플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다.
하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는 다익스트라 알고리즘(Dijkstra Algorithm)과 유사하며 다익스트라를 모든 정점에서 동작시키면 플로이드-워샬 알고리즘과 똑같이 동작하지만, 플로이드-워샬 알고리즘이 훨씬 간결하게 구현됩니다.
또한 다익스트라 알고리즘은 음수 간선치가 있을 시 제대로 동작하지 않지만, 플로이드-워샬 알고리즘은 음의 사이클만 없다면 음수 간선치가 있더라도 잘 동작합니다.
플로이드-워샬 알고리즘은 정점 N개의 그래프가 주어졌을 때, 모든 정점쌍 (i,j)에 대하여 k라는 경유지를 거쳤을 때, 기존의 정점쌍의 거리보다 짧아진다면, 정점쌍의 최단거리를 갱신시켜줍니다. 모든 최단거리는 음수 사이클이 없다면, 그 경로의 길이는 당연히 N이하가 되고 이를 이용해 동적계획법으로 해결 가능합니다.
아래 코드는 d[i][j] = i에서 j로가는 간선치로. 정의하는 인접행렬이 주어질 때 모든 쌍의 최단 경로를 구하는 부분코드입니다. 간선치의 합으로 인한 오버플로우와 중첩 포문의 첨자를 유의하여 실수 없이 코딩하는 것이 중요합니다.
더보기
입력 | 출력 |
첫번째 줄에 그래프의 크기 N이 주어지고, 두번째 줄부터 N + 1 줄 까지 인접행렬이 주어진다. 인접행렬의 값이 0이면 해당 경로가 없음을 의미한다. |
그래프의 모든 쌍의 최단경로를 인접행렬 형태로 출력한다. |
Sample Input | Sample Output |
4 0 1 4 0 2 0 2 3 4 1 0 2 1 1 3 0 |
3 1 3 4 2 3 2 3 3 1 3 2 1 1 3 4 |
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int d[][] = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
d[i][j] = scanner.nextInt();
if (d[i][j] == 0) d[i][j] = Integer.MAX_VALUE;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) continue;
if (d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
System.out.print(d[i][j] + " ");
System.out.println();
}
}
}