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

플로이드 와샬 알고리즘은 다익스트라, 벨만포드 알고리즘과는 달리 모든 정점간의 최단거리를 구하는 알고리즘입니다.

이 알고리즘은 동적 프로그래밍 기법을 사용한 알고리즘으로 O(V^3)이라는 시간복잡도가 필요하며, 다익스트라 알고리즘을 모든 정점 V만큼 반복한 것보다 더 빠릅니다. 또한 음의 가중치 간선은 존재할 수 있으나 음의 가중치 사이클은 없다고 가정합니다.

 

예시 그래프

# 경유점

경유점이라는 개념은 플로이드 와샬 알고리즘의 핵심입니다. 어떤 경로든 최단 경로사이의 경유지가 존재할 것입니다. 위 그래프를 가정하면 1->2를 가는 최단 경로는 (1->3->4->2)가 되고, 3, 4는 1->2사이의 경로에 존재하는 경유점이 됩니다.

즉, u->v로 가는 최단 경로가 있다면 이것은 크게 두가지로 나뉠겁니다.

1. 경로가 x를 경유하지 않는 것이 최단 경로이다. -> 이는 x를 제외한 정점들만이 경로에 포함될 것입니다.

2. 경로가 x를 경유한다. -> 이는 크게 보면 u->x로 가는 구간, x->v로 가는 구간으로 나뉩니다.

이렇게 보면 결국 모든 정점을 경유점으로 두어 계산하면 u->v로 가는 최단 경로를 구할 수 있게됩니다. 

즉, u에서 v로가는 점화식을 구하면

dp[u][v] = min(dp[u][v], dp[u][x] + dp[u][k])이고, x를 모든 정점에 대하여 반복 실행하면 됩니다.

 

# 소스코드

private static void floydWarshall(Graph graph, int N) {
        int [][] dp = new int[N+1][N+1];
 
        for (int[] d : dp)
            Arrays.fill(d, 999999);
 
        /**
         * 인접리스트로 만든 그래프의 경로를 배열에 넣어준다.
         * 인접행렬로 만든 그래프라면 그대로 써도 된다.
         */
        for (int i = 1; i <= N; i++) {
            dp[i][i] = 0;
            for (Node node : graph.sparseList.get(i)) {
                dp[i][node.v] = node.weight;
            }
        }
 
        /*
        k가 경유점일때 모든 i에서 j까지 가는 경로 갱신
        i -> j vs i-> k -> j
        */
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j =1; j<= N; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
 
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
 
    }

위 점화식을 그대로 코드로 옮겨 각 경유점에 대해 모든 정점간의 최단 경로를 구하고, 이 경유점을 모든 정점에 대해 반복해주면 됩니다.

위 예시그래프 실행결과

 

# 실제 경로 구하기

두 정점 사이의 최단경로의 실제 거쳐가는 경로를 구하기 위해서는 각 정점 쌍 u, v에 대해 마지막으로 dp[u][v]를 갱신할 때 사용한 경유점 k를 저장하면 됩니다. 이는, u에서 v를 가는 최단 경로가 k를 지난다는 의미이므로, u에서 k로 가는 최단 경로를 찾고, k에서 v로 가는 최단 경로를 찾아 합치면 됩니다. 소스코드로 보면 간단한데, 2차원 배열을 하나 더 만들어 dp[u][v]를 갱신할때 via[u][v] = k로 갱신하게 하고, 최종적인 결과를 재귀적으로 탐색하면 됩니다.

private static void floydWarshall(Graph graph, int N) {
        int [][] dp = new int[N+1][N+1];
        int [][] via = new int[N+1][N+1];
 
        for (int[] d : dp)
            Arrays.fill(d, 999999);
        for (int[] v : via)
            Arrays.fill(v, -1);
 
        /**
         * 인접리스트로 만든 그래프의 경로를 배열에 넣어준다.
         * 인접행렬로 만든 그래프라면 그대로 써도 된다.
         */
        for (int i = 1; i <= N; i++) {
            dp[i][i] = 0;
            for (Node node : graph.sparseList.get(i)) {
                dp[i][node.v] = node.weight;
            }
        }
 
        /*
        k가 경유점일때 모든 i에서 j까지 가는 경로 갱신
        i -> j vs i-> k -> j
        */
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j =1; j<= N; j++) {
                    if (dp[i][j] > dp[i][k] + dp[k][j]) {
                        via[i][j] = k;
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                    }
                }
            }
        }
 
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j<= N; j++) {
                if (i == j)
                    continue;
                ArrayList<Integer> list = new ArrayList<>();
                reconstruct(i, j, via, list);
                System.out.println(i+"->"+j +" : "+list);
            }
        }
 
    }
 
 
    /**
     * 재귀적으로 경로를 다시 찾으면서 list에 넣어준다.
     */
    private static void reconstruct(int u, int v, int[][] via, ArrayList<Integer> list) {
        if (via[u][v] == -1) {
            list.add(u);
            if (u != v) {
                list.add(v);
            }
        } else {
            int w = via[u][v];
            reconstruct(u, w, via, list);
            if (list.size() > 0)
                list.remove(list.size()-1);
            reconstruct(w, v, via, list);
        }
    }