Floyd-Warshall (플로이드-워샬 알고리즘)

플로이드-워샬 알고리즘(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();
        }
    }
}