다익스트라 알고리즘 with 우선순위 큐

우선순위 큐를 이용한 다익스트라 알고리즘의 구현. 출처는 책 알고리즘 트레이닝.

특이한 점으로는 pq에 동일한 원소들이 추가되도록 방치한다는 것이다.

어차피 나중에 continue가 포함된 if문에서 다 걸러지게 된다. 느긋한 삭제라고 부른다.

코드는 다음과 같다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <bits/stdc++.h> using namespace std;   typedef pair<int, int> ii;   // index는 0 ~ v - 1 // v은 vertex 갯수, s는 시작점 // edge에 (번호, 거리)로 저장   int v, s; vector<vector<ii>> edge(v);   vector<int> dist(v, INF); dist[s] = 0; priority_queue<ii, vector<ii>, greater<ii>> pq; pq.push(ii(0, s)); while (!pq.empty()) {     ii now = pq.top(); pq.pop();     int d = now.first, u = now.second;     if (d > dist[u]) continue;     for (ii e: edge[u]) {         if (dist[u] + e.second < dist[e.first]) {             dist[e.first] = dist[u] + e.second;             pq.push(ii(dist[e.first], e.first));         }     } }

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