[알고리즘/그래프] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

플로이드 와샬 알고리즘(Floyd Warshall Algorithm)이란?

---

음수 사이클이 없는 그래프에서 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘으로, 거쳐가는(경유) 정점을 기준으로 거쳐가는 경로가 기존의 경로보다 더 효율적인지 판단하여 최단 거리를 구한다.

정점의 개수만큼 3중 반복문을 수행하기때문에 O(V^3)만큼의 시간 복잡도를 갖는다.

• 동적 프로그래밍 기법을 사용한다.
• 음수 사이클이 존재하지 않으면 음의 가중치를 가질 수 있다. (≠ 다익스트라 알고리즘)

음수 사이클

이미지 출처 첨부

사이클의 모든 경로의 합이 음수가 되는 사이클이다.  1 --> 2 --> 3 --> 1의 경우, (1 -3 -2) = -4 이므로 음수 사이클이 존재한다.

 

구현 순서

1. 인접 행렬을 생성하고 간선의 정보를 저장한다. 인접 행렬에서 i번째 정점에서 j번째 정점으로 가는 가중치는D[i][j]이다.
2. 경유하는 정점을 기준으로, 어떤 두 정점이 해당 정점을 거쳐가는 경우 기존의 비용보다 더 작다면 기존의 거리 비용을 업데이트한다.
3. 모든 정점을 대상으로 3번의 과정을 반복한다.

구현 코드

public class FloydWarshall {
    static final int INF = 99999999; // 정점과 정점이 이어지지 않은 경우

    public static void main(String[] args) {
        int N = 4; // 정점의 개수
        int[][] D = {
                {0, 5, INF, 8},
                {7, 0, 9, INF},
                {2, INF, 0, 4},
                {INF, INF, 3, 0},
        };

        // 플로이드 와샬
        // k: 경유하는 노드, i: 출발 노드, j: 도착 노드
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    D[i][j] = Math.min(D[i][k] + D[k][j], D[i][j]);  // 경유하거나 직접가거나 더 짧은 경로로 대체
                }
            }
        }

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