[JAVA] 플로이드-와샬 알고리즘

플로이드-와샬 알고리즘이란?

• 음수 사이클이 없는 그래프에서 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘이다.
• 다익스트라 알고리즘과 다르게 음수 사이클만 존재하지 않으면 음의 가중치를 가질 수 있다.
• 음수 사이클 : 사이클의 모든 경로의 합이 음수가 되는 사이클
  • 1 → 2 → 1 사이클
    • -5 + 4 = -1
  • 1 → 2 → 3 → 1 사이클
    • 4 + -5 + -2 = -3

플로이드-와샬 알고리즘

플로이드-와샬 알고리즘은 다이나믹 프로그래밍을 사용한 알고리즘이며 인접 행렬을 이용하여 최단 거리를 계산한다. 또한 모든 정점에서 모든 정점으로 가는 최소 비용을 계산하기 위해서 모든 정점마다 순차적으로 갱신하면서 진행한다.

플로이드-와샬 알고리즘은 다음과 같은 순서로 진행된다.

1. 그래프의 인접행렬을 만든다. 인접행렬은 2차원의 형태이며 i번째 정점에서 j번째 정점으로 가는 가중치는 M[i][j]이다.

   1. 만약 i번째 정점에서 j번째 정점이 연결되어있지 않다면 무한대를 나타내는 값을 넣는다.
   2. 인접행렬에서 최단경로 행렬을 구한다.

2. 정점 i로부터 정점 j까지의 모든 경로 중에서 가장 짧은 경로의 거리는 $D_{ij}^{k}$라 한다.

3. 최단경로 행렬 D[i][j]는 다음과 같이 진행된다.

   Floyd_Warshall(D[][])
   FOR k in 1 → n
   FOR i in 1 → n (단, i ≠ k)
   FOR j in 1 → n (단, j ≠ k, j ≠ i)

       D[i][j] ← min(D[i][k] + D[k][j], D[i][j])

   • Line 1의 for문은 경유 가능한 정점을 1부터 n까지 확인하는 것이다.
   • Line 2~3 : 두 번째와 세 번째 for문은 점들의 각 쌍을 하나씩 고려하기 위한 루프이다.
     • 단, i = j, i = k, j = k인 경우는 제외
   • Line 4 : 점 i에서 점 j까지 점 k를 경유하는 거리와 점 i에서 점 j로 가는 경로 중 짧은 경로를 갱신한다.

시간복잡도

플로이드-와샬 알고리즘의 시간복잡도는 각 k에 대해 모든 i, j 쌍에 대해 계산되므로, 총 $n * n * n = n ^3$회 계산이 이루어지고, 각 계산은 $O(1)$ 시간 걸린다.

따라서 시간복잡도는 $O(n^3)$이다.

코드

import java.io.IOException;
import java.util.Arrays;

public class Floyd_Warshall {

    static final int INF = 99999999;

    public static void main(String[] args) throws IOException {
        // 정점의 수 입력
        int N = 4;

        // 인접 행렬 입력
        int[][] D = {{0, 2, 0, 15},
                     {0, 0, 10, 4},
                     {3, 0, 0, 0},
                     {0, 0, 7, 0}};

        // 갈 수 없는 경로 확인
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                if (D[i][j] == 0) D[i][j] = INF;
            }
        }

        // 입력 출력
        System.out.println("=============입력=============");
        for (int[] row : D) System.out.println(Arrays.toString(row));

        // 플로이드 와샬
        for (int k = 0; k < N; k++) {  // 경유 노드 확인
            for (int i = 0; i < N; i++) {  // 출발지
                if (i == k) continue;  // 출발지와 경유지가 같으면 다음 탐색
                for (int j = 0; j < N; j++) {  // 도착지
                    if (j == i || j == k) continue;  // 출발지와 도착지가 같거나 도착지가 경유지이면 다음 탐색
                    D[i][j] = Math.min(D[i][k] + D[k][j], D[i][j]);  // 경유하거나 직접가거나 더 짧은 경로로 대체
                }
            }
        }

        // 결과 출력
        System.out.println("=============결과=============");
        for (int[] row : D) System.out.println(Arrays.toString(row));
    }

}