[이취코] Ch09-1. 최단경로 / 다익스트라 알고리즘

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다
'길 찾기' 문제라고도 불리고, 최단 경로 알고리즘 유형에는 다양한 종류가 있는데 상황에 맞는 효율적인 알고리즘이 이미 정립되어있다

예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등 다양한 사례가 존재한다

최단 경로 문제는 보통 그래프를 이용해서 푸는데, 그래프에서 '노드' 는 각 지점을 의미하고 '간선' 은 지점 사이 연결 도로를 의미한다

최단 거리 알고리즘 중 많이 사용되는 알고리즘은 다익스트라 알고리즘이다
다익스트라 알고리즘에 대해 공부해보자
다익스트라 알고리즘은 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로도 볼 수 있다

 

다익스트라(Dijkstra) 최단 경로 알고리즘

: 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

- 매번 '가장 비용이 적은 노드'를 선택하기 때문에 그리디 알고리즘으로 분류
- '음의 간선'이 없어야함 (간선 모두 0 이상의 값을 가져야한다)

알고리즘의 원리
(1) 출발 노드를 설정한다
(2) 최단 거리 테이블을 초기화한다
(3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다
(4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다
(5) 3,4번을 반복한다

- '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트에 저장하며 리스트를 계속 갱신
- 이러한 1차원 리스트를 최단 거리 테이블이라고 한다

 

이런 그래프가 있고, 출발을 1에서 한다고 생각해보자
1번 노드에서 다른 모든 노드까지의 최단거리를 생각할 것이다

[초기상태]
- 다른 모든 노드로 가는 최단거리를 '무한'으로 초기화

[step 0]
- 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발노드를 선택

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한

[step 1]
- 1번 노드를 거쳐 다른 노드로 가는 비용 생각
- 갈 수 있는 노드 2, 3, 4
> 노드 2 : 0+2 = 2 (초기 상태 + 노드1에서 노드2까지 가는 비용)
> 노드 3 : 0+5 = 5 (초기 상태 + 노드1에서 노드3까지 가는 비용)
> 노드 4 : 0+1 = 1 (초기 상태 + 노드1에서 노드4까지 가는 비용)

- 테이블 초기화

노드 번호	1	2	3	4	5	6
거리	0	2	5	1	무한	무한

* 노란 숫자는 이미 방문한 숫자이다

테이블에서 노드 4로 가는 비용이 가장 적으므로 노드 4로 이동

[step 2]

 

- 노드 4에서 갈 수 있는 노드 3, 5 (노드 4까지 오는데 발생한 비용 + 새로 가는데 발생하는 비용)
> 노드 3 : 1 + 3 = 4  
> 노드 5 : 1 + 1 = 2

- 테이블 초기화

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

* 노드 3의 거리는 원래 5였으나 4가 더 작으므로 갱신해준다

초기화 후 거리가 가장 작은 노드는 2, 5다 -> 노드 2로 이동 (숫자가 더 작은 노드로)


[step 3]

- 노드 2에서 이동할 수 있는 노드 3, 4 (4는 이미 방문함)
> 노드 3 : 2 + 3 = 5

하지만 원래 3의 거리가 5보다 더 작은값이므로 갱신해주지 않는다 ( 거리가 더 작을 때만 갱신)

- 테이블 초기화

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

* 3의 거리는 그대로이다

다음으로 가장 작은 거리의 노드가 5이므로 노드 5로 이동한다

... 

이 과정을 반복하다보면 마지막으로 

 

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

모든 노드를 방문하게 되고 각 노드는 최소 비용을 갖는다
이 거리는 1번 노드로부터 출발했을 때 2번, 3번, 4번, 5번, 6번 노드까지 가기 위한 최단 경로가 각각 2, 3, 1, 2, 4 임을 의미한다

다익스트라 알고리즘에서 한번 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단거리가 줄어들지 않는다 (한 번 선택된 노드는 최단 거리가 감소하지 않는다)
-> 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다

 

구현

구현하는 데에는 두가지 방법이 있다
1. 간단하지만 느림
2. 조금 어렵지만 빠름

둘 다 해보자


① 간단한 다익스트라 알고리즘

- 시간복잡도 : O(v^2) 
* v = 노드의 개수 

- 각 노드에 대한 최단 거리를 담는 1차원 리스트 선언
- 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인 (순차 탐색)

#include <iostream>
#include <vector>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정

using namespace std;

int n, m, start; // 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)

// 노드의 개수는 최대 100,000개라고 가정
vector<pair<int, int> > graph[100001]; // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
bool visited[100001]; // 방문한 적이 있는지 체크하는 목적의 배열 만들기
int d[100001]; // 최단 거리 테이블 만들기

// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getSmallestNode() {
    int min_value = INF;
    int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
    
    for (int i = 1; i <= n; i++) {
        if (d[i] < min_value && !visited[i]) {
            min_value = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start) {
    // 시작 노드에 대해서 초기화
    d[start] = 0;
    visited[start] = true;
    for (int j = 0; j < graph[start].size(); j++) {
        d[graph[start][j].first] = graph[start][j].second;
    }
    
    // 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for (int i = 0; i < n - 1; i++) {
    
        // 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        int now = getSmallestNode();
        visited[now] = true;
        
        // 현재 노드와 연결된 다른 노드를 확인
        for (int j = 0; j < graph[now].size(); j++) {
            int cost = d[now] + graph[now][j].second;
            
            // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if (cost < d[graph[now][j].first]) {
                d[graph[now][j].first] = cost;
            }
        }
    }
}

int main(void) {
    cin >> n >> m >> start;

    // 모든 간선 정보를 입력받기
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].push_back({b, c});
    }

    // 최단 거리 테이블을 모두 무한으로 초기화
    fill_n(d, 100001, INF);
    
    // 다익스트라 알고리즘을 수행
    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리를 출력
    for (int i = 1; i <= n; i++) {
    
        // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if (d[i] == INF) {
            cout << "INFINITY" << '\n';
        }
        
        // 도달할 수 있는 경우 거리를 출력
        else {
            cout << d[i] << '\n';
        }
    }
}

- 시간 복잡도 : O(v^2)
> 총 O(v)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형탐색 해야하고, 현재 노드와 연결된 노드를 매번 일일이 확인해야하기때문

 

② 개선된 다익스트라 알고리즘

- 개선된 다익스트라 알고리즘은 힙을 사용해야한다 
- 글 길이상 다음 게시물에 작성하겠다!