[Algorithm] Floyd-Warshall's Algorithm (플로이드-와샬 알고리즘)

1. Floyd-Warshall's Algorithm

 

플로이드 와샬 알고리즘은 모든 정점간의 최단 거리를 구하는 All pairs shortest path solving 알고리즘이다.

플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 최단 거리를 구한다. 두 정점의 최단 거리를 구할 때 다른 모든 정점을 후보로 각 정점들을 거쳐갈 때의 거리를 비교하여 최소가 되는 경로를 찾는다.

소스 코드를 보면 가장 간단한 알고리즘이다.

 

 

2. 플로이드 와샬 알고리즘 구현

 

플로이드 와샬 알고리즘은 모든 정점 쌍에 대해서 다른 정점들을 중간 경로로 거치는 경로의 거리를 비교하여 최단 거리를 구한다.

 

1) 먼저 현재 그래프의 간선들을 기준으로 각 정점간의 거리를 저장할 행렬을 초기화한다.

2) 중간 경로가 될 정점을 선택한다.

3) 그래프의 모든 쌍을 반복하며 두개의 정점을 선택한다.

4) 선택된 두 정점의 현재 거리와 중간 경로가 될 정점을 거치는 경로를 비교한다. d(u, v)와 d(u, k) + d(k, v)를 비교한다.

5) 만약 현재 거리보다 다를 정점을 거치는 경로가 더 짧다면 최단 거리를 업데이트 한다.

6) 모든 정점이 한번씩 중간 경로가 되도록 2) ~ 5)를 반복한다.

 

    private void floydWarshall() {
        // 모든 정점이 한번씩 중간 경로가 되게 한다.
        for(int k = 0; k < N; k++) {
            // 그래프 내에서 될 수 있는 모든 정점 쌍 (i, j)를 구한다.
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    // 현재 (i, j)의 최단 거리와 k를 중간경로로 한 거리를 비교한다.
                    if(graph[i][j] < graph[i][k] + graph[k][j]) continue;
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }

- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Graph/FloydWarshall/FloydWarshall.java

 

 

3. 시간 복잡도

 

모든 정점 V에 대해서 그래프 내의 모든 정점 쌍을 구하는 반복 (V²)을 수행한다.

플로이드 와샬 알고리즘은 O(V³)의 시간 복잡도를 가진다.

 

 

[reference]

- https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/

Floyd Warshall Algorithm | DP-16 - GeeksforGeeks