개념

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

시간복잡도는 $O(E + V\log V)$이다.

동작 과정

처음 노드와의 최소 거리를 저장하는 dist변수를 각각의 노드에 둔다. 처음 노드는 0으로 다른 노드들은 임시적으로 INF를 부여한다.
처음 노드와 인접한 노드들간의 dist를 계산해서 넣는다. 인접 노드의 dist를 모두 계산했으면 현재 노드는 check(or visit)상태로 둔다. 이제 인접 노드들을 모두 dist가 적은 순서데로 나오게 할 Priority Queue에 넣는다. Priority Queue에는 노드와 그 노드의 dist를 같이 넣는다.
여기부터는 Priority Queue가 empty상태가 아닐때 까지 루프를 돈다.
1. Priority Queue에서 노드와 그 노드의 dist를 뽑아낸다. 이를 cur노드와 cur_dist라고 하자. 뽑아낸 노드는 check(or visit) 상태로 두고. 앞으로 방문하지도 PriorityQueue에 넣지도 않는다.
2. 이제 cur 노드의 인접한 노드들의 dist를 정해줄 차례이다. cur과 인접한 노드를 n, 그 노드와의 weight를 w라고 하자.
  
  아래는 거리(dist) 갱신의 과정이다.
  - 만약 노드n이 처음 방문한 노드라면 dist[n] = cur_dist + w 이다.
  - 만약 dist[n]이 이미 존재한 경우 dist[n]과 cur_dist + w 의 값을 비교해서 작은 값으로 변경한다.
3. 모든 인접노드들의 dist를 정해줬다면 Priority Queue에 인접노드와 그 인접노드의 dist를 넣는다. 이때 check(or visit)노드들은 제외한다.
굳이 visit을 사용하지 않고 3-2과정에서 갱신된 경우에만 Priority Queue에 넣어도 된다. 다만 이때는 모든 노드를 조사해야한다. 아래의 예제코드가 check를 사용하지 않은 경우이다.
도착점이 visit상태라면 알고리즘을 종료한다.

Python

quque 모듈의 PriorityQueue 를 사용해도 된다.

import sys
import heapq

I = sys.stdin.readline

v, e = map(int, I().split())
start = int(I())

graph = [[] for _ in range(v+1)]
dist = [0 for _ in range(v+1)]

for _ in range(e):
    s, d, w = map(int, I().split())
    graph[s].append((d, w))

pq = []
heapq.heappush(pq, (0, start))
while pq:
    cur_dist, cur = heapq.heappop(pq)
    for n, w in graph[cur]:
        if dist[n] == 0:
            dist[n] = cur_dist + w
            heapq.heappush(pq, (dist[n], n))
        elif dist[n] > cur_dist + w:
            dist[n] = cur_dist + w
            heapq.heappush(pq, (dist[n], n))

for i in range(1, v+1):
    if i == start:
        print(0)
    elif dist[i] == 0:
        print("INF")
    else:
        print(dist[i])

C++

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int V, e, k;
vector<pair<int, int>> node[20001];
bool check[20001];
int dist[20001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<pair<int, int>>::iterator it;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    cin >> V >> e;
    cin >> k;

    int u, v, w;
    for (int i = 0; i < e; i++) {
        cin >> u >> v >> w;
        node[u].push_back({v, w});
    }

    int min_dist;
    pq.push({0, k});
    while (!pq.empty()) {
        int current = pq.top().second;
        int cur_dist = pq.top().first;
        pq.pop();
        check[current] = true;
        for (it = node[current].begin(); it != node[current].end(); it++) {
            int n = (*it).first;
            int w = (*it).second;
            if (dist[n] == 0) {
                dist[n] = cur_dist + w;
                pq.push({dist[n], n});
            } else if (cur_dist + w < dist[n]) {
                dist[n] = cur_dist + w;
                pq.push({dist[n], n});
            }
        }
    }
    for (int i = 1; i <= V; i++) {
        if (i == k) {
            cout << "0\\n";
        } else if (dist[i] == 0) {
            cout << "INF\\n";
        } else {
            cout << dist[i] << '\\n';
        }
    }
}