문제 40
플로이드-워셜
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 양의 가중치 방향 간선으로 이루어진 그래프가 있다.
모든 정점 쌍 $(i, j)$에 대해 $i$번 정점에서 $j$번 정점으로 가는 최단 거리를 구하라.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 400; 0 \le M \le 100\,000)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 방향 간선의 시작 정점의 번호, 도착 정점의 번호, 가중치를 의미하는 세 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v; 1 \le w \le 10^9)$
같은 방향 간선은 두 번 이상 주어지지 않는다.
출력
$N$개의 줄에 걸쳐 모든 정점 쌍 사이의 최단 거리를 출력한다.
$i$번째 줄의 $j$번째 값에는 $i$번 정점에서 $j$번 정점으로 가는 최단 거리를 출력한다.
도달할 수 없는 경우에는 INF를 출력한다.
예제 입력 1
5 7 1 2 4 1 3 10 2 3 2 2 4 7 3 4 1 4 5 3 5 2 5
예제 출력 1
0 4 6 7 10 INF 0 2 3 6 INF 9 0 1 4 INF 8 10 0 3 INF 5 7 8 0
공식 해설
모든 정점 쌍의 최단 거리가 필요하고 $N\le400$이므로 플로이드–워셜 알고리즘을 사용한다.
처음에는 $D_{i,i}=0$, 직접 연결된 $i\to j$에는 간선 가중치, 나머지에는 무한대를 저장한다. 이후 중간 정점으로 사용할 수 있는 정점을 $1$개씩 늘린다.
$1$번부터 $k-1$번 정점까지만 중간에 쓸 수 있는 최단 거리를 알고 있다고 하자. $k$번 정점도 허용한 경로는 $k$를 거치지 않거나 $i\to k\to j$로 나뉘므로
\[
D_{i,j}\leftarrow\min(D_{i,j},D_{i,k}+D_{k,j})
\]
로 갱신한다. 이 의미가 유지되도록 $k$의 반복문을 가장 바깥에 둔다.
둘 중 한 거리가 무한대이면 덧셈하지 않는다. 모든 $k$를 처리한 뒤에도 무한대인 쌍에는 INF를 출력한다. 유한한 최단 거리는 $(N-1)\cdot10^9$ 이하이며, 갱신할 때는 두 거리의 합도 계산한다.
시간복잡도는 $O(N^3+M)$, 공간복잡도는 $O(N^2)$이다.
구현 · 언어별 풀이
C++ 구현
거리 배열을 long long으로 저장하고 대각선은 $0$, 나머지는 충분히 큰 값으로 초기화한다. 반복문의 순서는 중간 정점 $k$, 출발점 $i$, 도착점 $j$이다. 두 부분 경로가 모두 유한할 때만 합을 계산한다.
C 구현
long long 거리 행렬에 대각선 0을 넣고 k,i,j 순서로 갱신한다. 도달 불가능한 항을 제외한 뒤 합한다. 간선 가중치는 int지만 경로 길이는 그 범위를 넘는다.
Python 구현
행렬을 리스트의 리스트로 두고 k를 가장 바깥에 둔다. 안쪽 반복에서 row_i, row_k와 dist[i][k]를 지역 변수로 잡고 도달 불가능한 경우를 건너뛰면 $400^3$ 단계의 객체 접근 비용을 줄인다.
Java 구현
long[][] 거리 행렬을 사용한다. k,i,j 순서를 유지하고 두 거리가 유한할 때만 더한다. 큰 INF를 더해 오버플로시키지 않으며 대각선은 0으로 시작한다.
Rust 구현
Vec<Vec<i64>> 또는 평탄 Vec<i64>로 거리를 저장한다. k행 값을 읽은 뒤 갱신할 값을 계산하여 중첩 가변 borrow를 피한다. INF인 두 부분 경로는 합하지 않는다.
JavaScript 구현
거리 행렬은 Float64Array(n * n)에 두고 fill(Infinity) 후 대각선을 $0$으로 설정하면 된다. 유한 경로 길이는 $(N-1)\cdot10^9$ 이하이고 두 거리의 합도 Number로 정확하다.
$k$를 가장 바깥 반복문에 두고 i * n, k * n 같은 행 시작 위치와 dist[i*n+k]를 안쪽 반복 밖에서 읽는다. 둘 중 하나가 Infinity이면 건너뛴다. Int32Array로 거리를 저장하거나 비트 연산으로 합을 자르지 않는다. 출력에서 도달 불가능한 값만 INF로 표시한다.