플로이드 와샬(Floyd Warshall) 알고리즘

---

오늘은 플로이드 와샬(Floyd Warshall) 알고리즘에 대해서 포스팅 하겠습니다.

 

 

1. 플로이드 와샬 핵심 아이디어

플로이드 와샬(Floyd Warshall)도 다익스트라 알고리즘(Dijkstra algorithm)과 같이 특정 노드까지의 최단 거리를 구할 수 있는 알고리즘 입니다. 다익스트라 알고리즘(Dijkstra algorithm)은 one-to-all 알고리즘 입니다. 따라서 하나의 특정 노드로 부터 모든 노드까지의 최단 거리를 구할 수 있습니다. 하지만, 플로이드 와샬(Floyd Warshall) 알고리즘은 all-to-all 알고리즘 이므로, 모든 노드에서 부터 모든 노드 까지의 최단 거리를 구할수 있습니다. 

 

각 노드 마다의 거리를 2차원 배열로 표현해 주고, 자기 자신의 노드까지 거리는 '0', 갈수 있는 경로가 없으면 '무한'으로 표현해 줍니다.

 

 

 

위에서 작성한 2차원 배열을 기반으로 '거쳐 가는 노드' 들을 순회 하면서, 더 최소가 되는 거리로 2차원 배열을 업데이트 해줍니다. 먼저, 'A 노드를 거쳐서 목적지 까지 가는 경우'를 생각해 봅시다. (B -> C)로 가는 경우는 A를 거쳐 가게 되면, (B -> A -> C)가 됩니다. 따라서, (B -> C) vs (B -> A -> C) 두 거리 중 최소가 되는 값으로 2차원 배열을 업데이트 해줍니다. (B -> C) : 바로 갈수 있는 경로가 없으므로 '무한', (B -> A -> C) : 3 + 2 = 5 이므로, 5의 값이 더 작으므로 5로 2차원 배열의 해당 인덱스의 값을 업데이트 해줍니다. 이와 같은 방법으로 (C -> B) vs (C -> A -> B) 도 더 작은 값으로 업데이트 해줍니다. 

 

'B 노드를 거쳐 가는 경우'도 똑같이 업데이트 해줍니다. (A -> C) vs (A -> B -> C),  (C -> A) vs (C -> B -> A) 이 두 곳만 업데이트 해주면 되겠습니다.

 

 

 

마찬가지로, 'C 노드를 거쳐 가는 경우' 도 같은 방법으로 2차원 배열을 업데이트 해줍니다. (A -> B) vs (A -> C -> B),  (B -> A) vs (B -> C -> A) 이 두 인덱스만 업데이트 해주면 되겠습니다. 그러면 최종으로 all-to-all 2차원 최단거리 테이블이 완성 됩니다. 

 

 

2. Java 소스 코드

public class FloydWarshall {
    // 10억으로 무한 설정
    static final int INF = (int) 1e9; 

    public static void main(String[] args) {
        int[][] inputData = {
                {0, INF, 2},
                {3, 0, INF},
                {INF, 1, 0}
        };
        new All2AllShortestPathSolver(3).start(inputData);
    }
}

class All2AllShortestPathSolver {
    private int dimension;

    All2AllShortestPathSolver(int dimension) {
        this.dimension = dimension;
    }

    void start(int[][] inputDistances) {
        int[][] shortestDistances = new int[dimension][dimension];

        // 결과 그래프(shortestDistances)를 초기화
        for (int i = 0; i < dimension; i++) {
            for (int j = 0; j < dimension; j++) {
                shortestDistances[i][j] = inputDistances[i][j];
            }
        }

        // 3중 반복문 이므로, 시간 복잡도 O(n^3)
        // k = 거쳐가는 노드
        for (int k = 0; k < dimension; k++) {
            // i = 출발 노드
            for (int i = 0; i < dimension; i++) {
                // j = 도착 노드
                for (int j = 0; j < dimension; j++) {
                    shortestDistances[i][j] = Math.min(shortestDistances[i][j],
                            shortestDistances[i][k] + shortestDistances[k][j]);
                }
            }
        }

        // 결과를 출력
        for (int i = 0; i < dimension; i++) {
            for (int j = 0; j < dimension; j++) {
                if(shortestDistances[i][j] == FloydWarshall.INF)
                    System.out.print("Infinity");
                else
                    System.out.printf("%4d", shortestDistances[i][j]);
            }
            System.out.println();
        }
    }
}

 소스 코드를 보면 '거쳐가는 노드' 부터, '출발 노드', '도착 노드' 모두를 반복 하므로 3중 반복문이 사용 되었습니다. 따라서 시간 복잡도는 O(N^3)이 되겠습니다.