[알고리즘/C++] Dijkstra (다익스트라) Algorithm

• 다익스트라 알고리즘(Dijkstra Algorithm)은 어느 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 최단경로 알고리즘이다.
  
  
• 최단경로 알고리즘으로는 크게 3가지 종류가 있으며, 각 종류의 알고리즘마다 시간복잡도가 다르다. 알고리즘의 성질을 파악하고 이를 적재적소에 사용할 수 있는 것이 바람직하다.

1. 한 노드에서 다른 모든 노드까지의 최단경로 (One to Many)

• 다익스트라(dijkstra) 알고리즘과 벨만-포드(bellman-ford) 알고리즘이 있다.

• 다익스트라 알고리즘은 노드의 가중치가 양수일 때만 사용 가능한 알고리즘이다 (시간복잡도 : $O(NlogN)$)

• 반면, 벨만-포드 알고리즘은 노드의 가중치가 음수일 때도 사용 가능한 알고리즘이다. (시간복잡도 : $O(N^2)$)

• 노드간의 가중치가 모두 양수라면 다익스트라를 선택하면 되고, 음수가 존재한다면 벨만-포드를 선택하면 되겠다.

2. 모든 노드간의 최단경로 (Many to Many)

• 모든 노드로 나올 수 있는 노드 쌍에 대한 최단경로를 구하는 알고리즘은 플로이드 워셜(Floyd-Warshall) 알고리즘이다.

• 구현이 간단하며, 음의 가중치에서도 사용 가능하다.

• 시간복잡도가 $O(N^3)$인 단점이 있다.

3. 한 노드에서 다른 한 노드까지의 최단경로 (One to One)

• $A^*$알고리즘이 있다. 이는 다익스트라(Dijkstra) 알고리즘을 확장한 것이다.

• 다익스트라 알고리즘이 한 노드에서 다른 한 노드까지의 최단경로를 구하는 것을 포함하므로 $A^*$알고리즘 대신 다익스트라 알고리즘이 사용되는 경우가 많다.

---

다익스트라 알고리즘

• 위에서 언급했듯이, 한 노드에서 다른 모든 노드까지의 최단경로를 구하는 알고리즘이다.
  

• 다만, 이때 노드간의 가중치는 음수여서는 안된다.
  
  

• 기본적인 절차는 다음과 같다.

1. dist[n]이라는 노드의 최단경로 테이블을 생성하고, 이를 INF로 초기화 한다.
   
   dist[n]의 값들보다 작은 경로가 생기면 이를 반영해야 한다. 초반에 어떠한 값과 비교해도 기존 값이 커야하므로 INF 초기화하게 되는 것이다.
   
2. 현재 위치한 노드를 방문처리하고 인접 노드간의 거리를 계산하여 dist[n] 테이블을 갱신한다.
   
3. 인접 노드 중 거리가 가장 짧은 노드를 선택하여 방문처리한다.
   
4. 모든 노드를 방문할 때까지 2~3단계를 반복한다.
   

---

구현

* 이를 구현하는 방식은 인접 노드 중 최단경로 노드를 구하는 방식에 따라 두 가지가 있다.

1. 순차 검색
   
   인접 노드를 모두 탐색하여 최단경로 노드를 선택하는 방식이다. 이때 전체 노드의 개수(N)만큼 전체 노드가 해당 탐색을 필요로 하므로 시간복잡도는 $O(N^2)$가 됨을 알 수 있다.
   
   
2. 우선순위 큐(priority queue)
   
   최대 힙을 사용하여 큐에 넣을 때마다 자동으로 정렬되게 된다. 즉, 인접노드를 모두 탐색하지 않고도 최단경로를 가지는 노드를 받을 수 있는 것이다. 이때 pop()하면 인접 노드의 최단경로 노드를 구할 수 있다.
   
   우선순위 큐에 넣고 추출하는 연산은 $O(logN)$이므로 우선순위 큐를 사용하는 시간복잡도는 $O(NlogN)$이 됨을 알 수 있다.
   

---

• 우선 순위 큐를 사용한 구현은 아래와 같다.

  백준 문제 1916번이 전형적인 다익스트라를 구현해 푸는 문제이므로 해당 문제로 다익스트라 알고리즘을 구현하였다.
  
  백준 1916
  

#include <iostream>
#include <queue>
#define N 1001
#define INF 100000000

using namespace std;

vector<pair<int, int>> graph[N];
priority_queue<pair<int, int>> pq;
int dist[N];
int n, m;

void init_dist(int n) {
    for(int i = 1; i <= n; i++) dist[i] = INF;
}

void dijkstra(int start) {
    pq.push({0, start}); // 첫 노드 pq에 삽입 (거리는 0)
    dist[start] = 0;

    while(!pq.empty()) {
        int cur_dist = -pq.top().first;
        int cur_node = pq.top().second;
        pq.pop();
        
        if(dist[cur_node] < cur_dist) continue;

        for(int i = 0; i < graph[cur_node].size(); i++) {
            int nxt_node = graph[cur_node][i].first;
            int nxt_dist = dist[cur_node] + graph[cur_node][i].second;
            if(dist[nxt_node] > nxt_dist) {
                dist[nxt_node] = nxt_dist;
                pq.push({-nxt_dist, nxt_node});
            }
        }
    }
}
  
int main() {
    cin >> n >> m;

    int from, to, cost;
    for(int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost});
    }
    
    int start, dest;
    cin >> start >> dest;
    init_dist(n);
    
    dijkstra(start);
    cout << dist[dest];
    return 0;
}

• 우선순위 큐인 pq에 값을 {거리, 노드} 순으로 삽입을 진행한다. 이때 우선순위 큐는 최대 힙이 아닌 최소 힙이므로 {-거리, 노드}로 값을 푸쉬해야 가장 작은 거리부터 순서대로 pop()할 수 있다.
  
• 시작 노드부터 다른 모든 노드까지의 최단거리를 갱신하여 저장하는 dist[n]을 꼭 INF로 초기화해야한다. 그렇지 않으면 처음에 값을 갱신하고 싶어도 dist[n]보다 커 갱신이 되지 않는 경우가 발생할 수 있기 때문이다.
  
• 큐(우선순위 큐)를 사용하는 것이 BFS와 닮아있기도 하다. 처음에 시작할 노드를 push해주고 큐가 빌 때까지 while문에서 연산을 진행하는 것을 볼 수 있다.