최단 거리 알고리즘 - Floyd - Warshall 알고리즘

Floyd - Warshall 알고리즘

• 이전에 각각 살펴봤던 Dijkstra, Bellman - Ford 알고리즘은 시작 지점이 존재하고, 해당 지점에서 각 노드로의 최단 경로를 구하는데 사용하는 알고리즘이다.
• Floyd - Warshall 알고리즘은 모든 노드에 대해서 각 노드에 대한 최단 거리를 구하는 알고리즘이다. 쉽게 말하자면 모든 노드에 대하여 Dijkstra나 Bellman - Ford를 돌려보았다고 생각하면 좋다.
• 다만 구현 방법은 순수 DP를 사용한다는 것이 차이점이다. Floyd - Warshall 알고리즘 역시 음의 가중치가 존재해도 사용이 가능하며, Bellman - Ford와 동일하게 음수 사이클이 존재한다면 사용할 수 없다.

 

 

Floyd - Warshall 알고리즘의 원리

• DP를 사용한다고 서술했다. 다만 이전에 한 노드에서 출발하여 다른 노드로 가는 최단 경로를 저장하는 1차원 배열이 DP-Table이었던 것과는 다르게, 모든 노드에 대해 다른 노드에 대한 최단 거리를 구해야 하므로 2차원 배열이 DP-Table이 된다.
• 먼저 아래와 같은 그래프가 있다고 가정하자.

• 가장 먼저 DP-Table을 구성해야 한다. 자기 자신에 대해 이동하는 것은 가중치가 0인게 자명하기 때문에 table의 동일한 행열은 0으로 만들고, 나머지는 INF로 설정한다.

• 이제 초기값을 넣어줄 차례이다. 먼저 각 노드에 대해 인접한 노드들을 가지고 최단 경로들을 만들어 준다. 예를 들어 1에서 3으로 가는 것은 2라는 가중치의 간선이 존재하기 때문에 $D_{13} = 2$가 될 것이다. 이를 반복하면 DP-Table은 아래와 같게 될 것이다.

• 이제 아래와 같은 과정을 진행한다.
  • 어떤 노드 $V_i$에서 $V_j$로 이동할 때, 다른 노드 $V_k$를 경유해서 갈 수 있다면 다음이 성립한다.
    • $D_{ij} = \min(D_{ij}, D_{ik} + D_{kj})$ 단, $D_{ik} \neq \infty, D_{kj} \neq \infty$
  • 제약사항은 경유할 노드 $V_k$가 존재할 때 $V_I, V_j$에서 $V_k$로 가는 간선이 존재해야 한다는 것을 의미한다.
  • 위의 연산을 모든 노드에 대해 수행한다.
• 먼저 $V_k$가 1일때를 가정한다. 예를들어 4번 노드에서 3번 노드로 가는 최단 경로에서 1번 노드를 경유해서 가는 경우를 생각해 보자.
  • $D_{43} = \min(D_{43}, D_{41} + D_{13})$이 되고 $D_{43} = \min(-1, -3 + 2)$로 갱신이 일어나지 않는다.
• 이외에 다른 경유하는 경로는 없어 보인다. 그럼 예를 들어 $V_k$가 3일떄를 생각해보자 4번 노드에서 3을 경유하여 7로 가는 것을 생각해보자.
  • $D_{47} = \min(D_{47}, D_{43} + D_{37})$이 되고 $D_{47} = \min(\infty, -1 + 4)$가 되고 3으로 업데이트가 일어난다.
• 이러한 과정을 $k = 1 ... 7$까지 수행하는 것이다. 이를 구현한 코드는 아래와 같다.

// 알고리즘 - 최단 경로 알고리즘
// 플로이드-워셜

public class Main {
    static int[][] dist;
    static final int INF = 1000000000;
    public static void floydWarshall(int v, int e, int[][] data, int start) {
        dist = new int[v + 1][v + 1];

        // initialize dist
        for (int i = 1; i < v + 1; i++){
            for (int j = 1; j < v + 1; j++){
                if (i != j){
                    dist[i][j] = INF;
                }
            }
        }

        for (int i = 0; i < e; i++){
            dist[data[i][0]][data[i][1]] = data[i][2];
        }

        //floyd - warshall
        for (int k = 1; k < v + 1; k++){
            // i -> j (k를 경유해서 가는 경우가 더 짧으면 업데이트)
            for (int i = 1; i < v + 1; i++){
                for (int j = 1; j < v + 1; j++){
                    // 만약 i번 노드에서 k번 노드를 거쳐서 j번 노드로 이동이 가능한 경우
                    if (dist[i][k] != INF && dist[k][j] != INF){
                        //i번 노드에서 j번 노드로 가는 최단 경로는 i번 노드에서 j번 노드로 가는 직통 경로의 가중치와 경유한 경로의 가중치 합
                        //중 더 작은 가중치가 된다.
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        for (int i = 1; i < v + 1; i++){
            for (int j = 1; j < v + 1; j++){
                if (dist[i][j] >= INF){
                    System.out.printf("%5s ", "INF");
                } else{
                    System.out.printf("%5d ", dist[i][j]);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // Test code
        int[][] data = {{1, 2, 8}, {1, 3, 6}, {1, 5, 5}, {2, 3, -5}, {2, 4, 1}, {2, 6, 4}, {3, 4, 4}, {4, 7, 3}, {5, 6, 5}, {6, 2, 0}, {6, 7, -7}};
        floydWarshall(7, 11, data, 1);
        System.out.println();

        data = new int[][]{{1, 2, 8}, {1, 3, 6}, {1, 5, 5}, {2, 3, -5}, {2, 4, 1}, {2, 6, 4}, {3, 4, 4}, {4, 7, 3}, {5, 6, 5}, {6, 2, -5}, {6, 7, -7}};
        floydWarshall(7, 11, data, 1);
    }
}

 

 

 

Floyd - Warshall에서의 음수 사이클 문제

• Floyd - Warshall 알고리즘도 음수 사이클이 존재하는 그래프에서는 사용이 불가능하다. 이를 검출하기 위해서 Bellman - Ford 알고리즘과는 조금 다른 방식을 사용한다.
• 위의 DP-Table에서 자기 자신으로 돌아오는 모든 가중치는 0으로 되어있다. 하지만 음수 사이클이 존재하는 경우에 자기 자신으로 다시 되돌아오는 최단 경로가 음수가 된다.
• 따라서 해당 DP-Table을 스캔하여 행과 열이 동일한 곳의 값이 음수가 되어있다면, 음수 사이클이 존재한다는 것으로 판단할 수 있다.

public static boolean hasMinusCycle(int[][] table){
    for(int i = 0; i < table.length; i++){
        for(int j = 0; j < table[i].length; j++){
            if(i == j && table[i][j] < 0) return false;
        }
    }
    
    return true;
}

 

 

 

Floyd - Warshall 알고리즘의 시간복잡도

• 모든 정점을 경유해서 가는지를 탐색하고, 경유해서 가는것을 탐색하는데 각각의 정점 모두를 검사하기 때문에 3중 루프가 사용된다.
• 따라서 시간복잡도는 $O(V^3)$이 된다.

 

 

 

마무리

• 최단 경로 문제에 대한 3개의 알고리즘을 알아보았다.
• 시간복잡도 상으로 양수 가중치만 존재하는것이 증명된다면 다익스트라를 사용하는 것이 가장 좋다. 만약 모든 정점에 대해 최단 거리를 구한다고 가정하더라도 $O((V^2 + VE) \log V)$ 정도로, Floyd - Warshall 보다 근소하게 앞서는 시간복잡도를 가진다.
• 만약 음수 가중치가 존재한다면 Bellman - Ford를 사용한다. 만약 음수 가중치가 존재하면서 모든 정점간의 최단 거리를 구해야 할 경우 Floyd - Warshall을 사용하는 것을 고려할 수 있다.