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

그래프에서 정점끼리의 최단 경로를 구하는 방법은 여러가지가 있다.

• 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제
• 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
• 하나의 목적지로 가는 모든 정점까지의 최단 경로를 구하는 문제
• 모든 최단 경로를 구하는 문제 (플로이드-와샬)

 

플로이드-와샬(Floyd-Warshall Algorithm)

플로이드 와샬 알고리즘은 동적 계획법(DP)의 한예로, 로버트 플로이드가 1962년에 발표했다.

이 알고리즘의 삼중 for 반복문의 공식은 Peter Ingerman 이 설명했다.

 

변의 가중치가 음수 또는 양수인 (음수 사이클이 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.

알고리즘을 한 번 수행하면, 모든 정점 쌍간의 최단 경로의 길이(가중치의 합)을 찾는다.

알고리즘 자체는 경로를 반환하지 않지만, 알고리즘을 약간만 변형 시키면 경로를 찾을 수 있다.

* 음수 사이클 : 사이클의 모든 경로의 합이 음수가 되는 사이클 (즉, 가중치를 더했을 때, 이동간 값이 음수가 나오는 경우를 말함)

 

다음 아래는 의사코드이다.

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3    dist[u][v] ← w(u,v)  // 변 (u,v)의 가중치
4 for each vertex v
5    dist[v][v] ← 0
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j]
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

 

시간복잡도 : O(V³)

 

[Java 로 구현]

package algorithm;

import java.util.Arrays;

public class 플로이드와샬 {
    static final int INF = 1_000_000_000;
    public static void main(String[] args) {
        int[][] inputData = {
                                 {1,2,1},
                                 {2,3,3},
                                 {5,2,2},
                                 {1,4,2},
                                 {5,3,1},
                                 {5,4,2},
                            };

        int n = 5;
        solution(n, inputData);
    }

    static void solution(int n, int[][] input) {
        //1. 2차원 배열 생성(기본조건)
        int[][] floyd = new int[n][n];

        //2.
        for (int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // 출발정점과 도착정점이 같을 땐 가중치가 0
                if(i == j) {
                    floyd[i][j] = 0;

                // 일단 비교하더라도 큰 수인 높은 수로 초기화를 시킴
                }else {
                    floyd[i][j] = INF;
                }
            }
        }

        //3. input 받은 값에서 각 정점의 가중치 잇기 (idx 맞추기 위해 '-1' 을 함)
        for (int i = 0; i < input.length; i++) {
            floyd[input[i][0] - 1][input[i][1] - 1] = input[i][2];
        }

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


		//4. 플로이드 와샬 알고리즘 적용
        // k : 거처가는 노드
        for (int k = 0; k < n; k++) {
            // i : 출발 노드
            for (int i = 0; i < n; i++) {
                if (i == k) continue; // 출발지와 경유지가 같다면 pass
                // j : 도착 노드
                for (int j = 0; j < n; j++) {
                    if (i == j || j == k) continue; // 출발지와 도착지가 같거나, 도착지가 경유지면 pass
                    // 비교 작업이 필요.
                    // i -> j  VS  i -> k(경유지) -> j
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }

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