최단 경로 문제 (3) 플로이드-워셜 알고리즘을 중심으로

1. 들어가기

     지난 글에서는 경로의 가중치가 음수로 부여된 경우에 사용되는 벨만-포드 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 사용하는 알고리즘이긴 하나, 모든 노드간 최단 거리를 탐색하는 알고리즘인 플로이드-워셜(Floyd-Warshall)에 대해 알아볼 것이다. 
 

2. 플로이드-워셜(Floyd-Warshall)

     플로이드-워셜 알고리즘으 모든 정점의 쌍 사이에 최단 경로를 구할 수 있다. 다만, 음의 가중치의 순환(음수 사이클)이 없다는 가정 하에서 구할 수 있다. 모든 쌍의 최단 경로는 최단 경로의 부분 경로이므로, 경로의 부분 경로가 모여 곧 최단경로가 되는 형태이다. 그러므로 최단 경로를 구하는 상향식 접근방법이라 볼 수 있다.

     플로이드-워셜 알고리즘은 모든 정점의 쌍을 확인하므로 느리다. 시간 복잡도는 O(V^3); V는 꼭짓점(노드)의 수 이다. 시간복잡도가 O(V^3)이 된 원인으로는 삼중 for문으로 중간 정점을 거치기 때문이다. 다중 for문으로 복잡할 것 같지만 선형 자료구조가 중첩된 형태이고, 복잡한 자료구조를 사용하지 않기 때문에 직관적으로 이해할 수 있는 형태이다. 플로이드 워셜 알고리즘의 문제라면 메모리 사용량이지, 수행 시간부분에서는 매우 빠르고, 타 최단경로 알고리즘보다 효율적이다.
 

[그림 1] 그래프

 그래프가 위 [그림 1]과 같이 존재한다고 하면, A 에서 각 점까지의 최단 경로 쌍은 다음과 같이 구할 수 있다.

3. 정리

플로이드-워셜 알고리즘을 적용하여 최단거리 문제를 풀면 다음과 같은 절차를 거친다.

1) 경로 내 음수 사이클이 존재하는 지를 확인(존재하면 시작 점에서 각 점마다 이동하는 최단 경로를 구할 수 없음)
2) 최소 거리값을 할당할 배열을 선언하고, 모든 점에 매우 큰 값인 INF를 할당함.
3) 모든 노드 쌍 간에 거리 비교 시 중간 노드를 거쳐가는 형태로 값을 비교하여 더 작은 값을 배열에 할당함.
4) 모든 꼭짓점마다 노드 쌍의 최소 거리를 모두 구한다. 
 

4. 구현

public class Main {
    static int[][] dist;
    static final int INF = (int) 1e9; // 오버플로우가 나지 않고 경로를 구하는 범위 상에서 충분히 큰 값으로 설정함.

    public static void floydWarshall(int v, int e, int[][] data) {
        dist = new int[v][v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; 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];
        }

        for (int k = 0; k < v; k++) {
            // 경유점
            for (int i = 0; i < v; i++) {
                for (int j = 0; j < v; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF && i!=j) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; 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) {
        int[][] data = new int[][]{{1, 2, 5}, {1, 3, 1}, {3, 4, 2}, {2, 4, 1}, {2, 6, 3}, {2, 7, 3}, {4, 5, 5}, {4, 6, 3}, {6, 7, 2}};
        floydWarshall(7, 9, data);
        
        /*
        
    0     5     1     3     8     6     8 
  INF     0   INF     1     6     3     3 
  INF   INF     0     2     7     5     7 
  INF   INF   INF     0     5     3     5 
  INF   INF   INF   INF     0   INF   INF 
  INF   INF   INF   INF   INF     0     2 
  INF   INF   INF   INF   INF   INF     0 
  
        */
    }
}

 

5. 플로이드-워셜 구현 시 유의할 점

- 음수 사이클이 존재하는 경우에는 최단경로를 구할 수 없음에 유의한다.

- 플로이드-워셜 알고리즘은 경유점에 거치는 계산으로 O(V^3)의 시간복잡도를 갖는다.

- 각 점들의 최단경로의 거리는 INF로 초기화 한다.

- 시작 점으로부터 연결된 경로가 없는 경우 값이 INF로 할당되어 있다.

 
참고문헌 : Introduction to algorithms 3rd edition, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 2