문제 38
다익스트라
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 양의 가중치 간선으로 이루어진 무방향 그래프가 있다.
시작 정점 $S$로부터 각 정점까지의 최단 거리를 구하라.
입력
첫 번째 줄에 세 정수 $N$, $M$, $S$가 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; 0 \le M \le 200\,000; 1 \le S \le N)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 간선의 양 끝 정점의 번호와 가중치를 의미하는 세 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^9)$
같은 두 정점을 연결하는 간선은 두 번 이상 주어지지 않는다.
출력
$1$번 정점부터 $N$번 정점까지 시작 정점 $S$로부터의 최단 거리를 한 줄에 하나씩 출력한다.
시작 정점에서 도달할 수 없는 정점이라면 -1을 출력한다.
예제 입력 1
5 6 1 1 2 2 1 3 5 2 3 1 2 4 2 3 5 3 4 5 1
예제 출력 1
0 2 3 4 5
공식 해설
가장 가까운 후보부터 확정하기
모든 간선의 가중치가 양수이므로 다익스트라 알고리즘을 사용한다. $d_v$를 지금까지 발견한 $S$에서 $v$로 가는 경로 길이의 최솟값으로 둔다. $d_S=0$, 나머지는 무한대로 초기화하고 최소 힙에 $(0,S)$를 넣는다.
힙에서 $(d,u)$를 꺼냈을 때 $d\ne d_u$이면 더 짧은 경로를 이미 찾은 오래된 후보이므로 건너뛴다. 그렇지 않으면 $u$의 각 이웃 $v$에 대해 $d_u+w<d_v$일 때 거리를 갱신하고 새 후보를 넣는다. 무방향 간선은 양쪽 인접 리스트에 저장한다.
먼저 꺼낸 거리가 최단 거리인 이유
가장 작은 유효 후보 $u$에 더 짧은 경로가 있다고 하자. 그 경로에서 아직 확정하지 않은 첫 정점은 앞의 확정된 정점에서 이미 후보로 등록되었다. 남은 간선의 가중치가 양수이므로 그 후보의 거리는 $u$보다 작아야 한다. 그런데 $u$가 먼저 꺼내졌으므로 모순이다.
따라서 위 완화를 반복하면 도달 가능한 모든 정점의 최단 거리가 구해진다. 끝까지 무한대인 정점에는 $-1$을 출력한다. 유한한 최단 거리는 최대 $(N-1)\cdot10^9$이므로 개별 간선 가중치보다 넓은 범위를 고려한다.
시간복잡도는 $O(N+M\log(N+1))$, 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
인접 리스트에 도착 정점과 가중치를 저장하고 거리는 long long으로 둔다. 힙에는 (거리, 정점)을 넣고 priority_queue의 비교자로 greater<>를 지정해 최소 힙으로 만든다. 힙에서 꺼낸 후보의 거리가 최신 거리와 다르면 건너뛴다.
무한대는 유한한 최단 거리의 상한보다 크면서 간선 가중치를 더해도 overflow하지 않는 값으로 둔다. 예를 들어 1LL << 62를 사용할 수 있다. 도달하지 않은 정점은 힙에 넣지 않는다.
C 구현
인접 간선을 배열에 저장하고 (거리,정점)의 최소 힙을 직접 구현한다. dist는 long long으로 두고 꺼낸 거리가 현재 dist와 다르면 건너뛴다. C 표준에는 힙 컨테이너가 없으므로 이 구현이 필요하다.
Python 구현
heapq에 (거리,정점)을 넣고 dist와 다른 오래된 항목은 버린다. 거리는 Python int로 계산한다. 도달 불가능 표시를 충분히 큰 정수로 두고 그 정점에서는 덧셈하지 않는다.
Java 구현
PriorityQueue<long[]>에 거리와 정점을 넣고 Long.compare로 거리 순서를 정한다. dist는 long[]이며 stale 항목을 건너뛴다. 정점마다 새 Solver나 별도의 상태 관리자 객체는 필요 없다.
Rust 구현
BinaryHeap<Reverse<(i64,usize)>>를 사용한다. 표준 힙은 최대 힙이므로 Reverse가 필요하다. dist와 다른 항목은 건너뛰고, 도달한 정점의 거리만 간선 가중치와 더한다.
JavaScript 구현
최단 거리는 $(N-1)\cdot10^9<10^{14}$이므로 Float64Array 또는 일반 숫자 배열로 정확히 저장할 수 있다. 도달 불가능은 Infinity로 두고 실제 거리와 구분한다. 32비트 Int32Array에는 거리 합이 들어가지 않는다.
Node.js에는 기본 우선순위 큐가 없으므로 [거리, 정점]을 저장하는 최소 이진 힙을 사용한다. 삽입은 부모보다 작은 후보를 위로 올리고, 삭제는 마지막 후보를 루트에 넣어 더 작은 자식 쪽으로 내린다. 꺼낸 거리와 dist[u]가 다르면 오래된 후보를 버린다. 정점 번호가 아니라 거리를 기준으로 비교하며, 갱신될 때만 새 후보를 넣는다.