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

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

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

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

코드는 다음과 같다.

#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})$이다.