[Algorithm] 다익스트라 알고리즘 (Dijkstra's Algorithm)

• 음의 가중치가 없는 그래프에서 최단거리를 구하는 알고리즘이다.
  음의 가중치를 가지는 간선이 존재하면 거리의 합이 음수 무한대로 발산하기 때문에 이 알고리즘은 사용할 수 없다.
• 에츠허르 다익스트라가 고안한 알고리즘은 $ O(V^2) $ 의 시간 복잡도를 가진다. (V : 정점(vertex)의 개수)
• 우선순위 큐(힙 트리)를 이용한 개선된 알고리즘에서는 $ O((V + E)  logV) $의 시간복잡도를 가진다. (V : 정점(vertex)의 개수, E : 간선(edge)의 개수)

 

알고리즘

1. 시작 정점과 도착 정점을 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 현재 정점에서 인접한 정점 중 "미방문" 상태인 정점들을 찾고, 거리를 비교하여 최단 거리 테이블을 업데이트한다.
4. 현재 정점을 "방문 완료" 상태로 바꾸고, "미방문" 상태인 정점 중 시작점과의 거리가 가장 짧은 정점을 골라 현재 정점으로 설정한다.
5. 현재 정점이 도착 정점이거나, 더이상 선택할 수 있는 "미방문"상태인 정점이 없을 때까지 3~4를 반복한다.

 

그림 예시

 

시작 정점을 정점 1로, 도착 정점을 정점 6으로 설정하고
최단 거리 테이블을 초기화한다.
이때 inf는 infinite 무한대를 뜻한다.

 

 

 

 

 

 

시작 정점을 선택하고, 거리를 0으로 업데이트한다.

 

 

 

 

 

 

 

 

 

정점 1과 인접한 정점은 2, 3, 4이다.
각 정점마다 기존의 거리값과 현재 걸리는 거리값을 비교하여
최솟값으로 최단 거리 테이블를 업데이트한다.

 

 

 

 

 

 

 

 

1번 정점을 방문완료 상태로 바꾼다.

시작 정점에서의 거리가 가장 짧은 2번 정점을 현재 정점으로 설정한다.
그 다음 2번 정점에서 인접한 정점 중 미방문상태인3, 5번 정점이다.
3, 5번 정점까지의 거리를 계산하여 테이블을 업데이트한다.
(3~4 반복 작업)

 

 

2번 정점을 방문완료 상태로 바꾼다.
미방문 상태인 정점 중 거리가 가장 짧은 정점은 4번 정점이다.
4번 정점을 현재 정점으로 설정하.
4번 정점에서 인접한 정점인 3, 5, 6번 정점이다.
각 정점까지의 거리를 계산하여 테이블을 업데이트한다.
(3~4 반복 작업)

4번 정점을 방문완료 상태로 바꾸고,
시작 정점에서 정점까지의 거리가 가장 짧은 3번 정점을 현재 정점으로 설정한다.
3번 정점에서 인접한 미방문 정점인 5번 정점까지의 거리를 계산하여,
최단 거리 테이블을 업데이트한다.
(3~4 반복 작업)

 

 

 

3번 정점의 상태를 방문 완료로 바꾸고, 현재 정점을 5번 정점으로 설정한다.
5번 정점에서 갈 수 있는 6번 정점에 대해 거리를 계산하고, 테이블을 업데이트 한다.
(3~4 반복 작업)

 

 

 

 

 

 

 

5번 정점에 대해 방문 완료 상태로 바꾸고, 현재 정점을 6번 정점으로 설정한다.
도착 정점이 현재 정점이 되었으므로 반복을 중지한다.
시작 정점에서 도착 정점까지의 최단 거리는 9이다.

 

 

 

 

 

 

 

우선 순위 큐를 이용한 코드 구현

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int main(){
    int V, E;
    cin >> V >> E;
    vector<pair<int, int>> graph[V];

    int v1, v2, cost;
    for(int i=0; i<E; i++){
        cin >> v1 >> v2 >> cost;
        graph[v1].push_back({cost, v2});
        graph[v2].push_back({cost, v1});
    }

    int start, goal;
    cin >> start >> goal;
    
    // start of dijkstra
    vector<int> dist(V+1, INF);
    priority_queue<pair<int, int>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while(!pq.empty()){
        int curr_dist = pq.top().first;
        int curr_node = pq.top().second;
        pq.pop();

        for(int i=0; i<graph[curr_node].size(); i++){
            int next_dist = graph[curr_node][i].first + curr_dist;
            int next_node = graph[curr_node][i].second;

            if(next_dist < dist[next_node]){
                dist[next_node] = next_dist;
                pq.push({next_dist, next_node});
            }
        }

        for(int i=1; i<=V; i++) 
            if(dist[i] == INF) cout << "INF\t";
            else cout << dist[i] << "\t";
        cout << "\n";
    }
    // end of dijkstra 

    cout << start << " 정점에서 " << goal << " 정점까지의 최단거리는 " << dist[goal] << "\n";
}

입력

6 10
1 2 1
1 3 5
1 4 4
2 3 7
2 5 8
3 4 9
3 5 2
4 5 4
4 6 9
5 6 2
1 6

출력 결과

0       1       5       4       INF     INF
0       1       5       4       7       INF
0       1       5       4       7       9
0       1       5       4       7       9
0       1       5       4       7       9
0       1       5       4       7       9
1 정점에서 6 정점까지의 최단거리는 9