간선에 가중치가 있는 그래프에서 1:N 최단 거리를 구하는 알고리즘입니다. 보통 가중치가 없는 그래프에서의 1:N 최단거리는 BFS(O(V+E))를 통해서 계산하고, 가중치가 있는 그래프에서 N:N 최단거리는 플로이드 워셜(O(N^3)) 으로 계산합니다. 단, 다익스트라를 포함한 위의 알고리즘은 가중치가 음수 일때는 사용하지 못합니다. 가중치가 음수일 경우 벨만포드 알고리즘이나 SPFA를 통하여 최단거리를 구해야 합니다. 최단 거리를 기록할 배열과 후부가 될 수 있는 간선 중 최고로 작은 간선을 빠르게 뽑아낼 수 있는 힙 자료구조가 필요합니다. 우선 힙은 두 가지 정보를 저장합니다. 1번 정점으로 부터의 거리와 정점의 번호입니다. 맨 처음 힙에는 0,1 이 들어갑니다. 1번 정점이 1번 정점으로부터 0만큼 떨어져 있습니다. pq에 삽입될 수 있는 정점이 최대 V^2이므로 log(V^2)->2*log(V) -> log(V) 번 pq에서 top을 꺼내게 됩니다. 이후 거리를 갱신하기 위해 간선을 보는데 E번 이루어지기 때문에 총 시간 복잡도는 O(Elong(V)가 됩니다. 예제 문제 백준 1753번 최단경로 |
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 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <cstdio> #include <algorithm> #include <queue> #include <vector> #include <cstring> using namespace std; int v, e, s, x, y, z, d[20002]; vector<vector<pair<int, int>>> vt; int main() { scanf("%d%d%d", &v, &e, &s); vt.resize(v + 1); for (int i = 0; i < e; i++) { scanf("%d%d%d", &x, &y, &z); vt[x].push_back({ y,z }); } memset(d, -1, sizeof(d)); priority_queue<pair<int, int>> pq; pq.push({ 0,s }); while (pq.size()) { int here = pq.top().second; int cost = -pq.top().first; pq.pop(); if (d[here] != -1) continue; d[here] = cost; for (auto it : vt[here]) { int next = it.first; int acost = -it.second - cost; if (d[next] != -1) continue; pq.push({ acost, next }); } } for (int i = 1; i <= v; i++) { if (d[i] == -1) puts("INF"); else printf("%d\n", d[i]); } return 0; } | cs |