플로이드 와샬 : Floyd Warshall

플로이드 와샬 : Floyd Warshall

가중치가 있는 그래프에서 모든 정점의 쌍에 대해 최단 경로를 찾는 알고리즘

* 플로이드 와샬 알고리즘은 다이나믹 프로그래밍의 한 예로 핵심 아이디어는 아래와 같다.

어떤 두 정점 사이의 최단 경로는 어떤 경유지를 거치거나 거치지 않는 경로 중 하나

예시

그래프에 따른 초기 최단 경로 배열

위와 같은 그래프가 있을 때, 각 정점에서 정점으로의 최단 경로를 나타내는 배열은 우측과 같다.

자기 자신은 0이고 간선이 존재하지 않는다면 INF를 넣어준다.

모든 경로에 대해 경유지 K를 거쳐갔을 때와 비교해가며 최단 경로를 계산해준다.

-> A-B와 A-K + K-B를 비교한다.

* 특징

- 모든 가능한 경유지에 대해 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 확인하므로 O(n^3)가 걸린다.
- 방향이 있는 그래프와 방향이 없는 그래프에서 다 사용 가능하다.
- 음의 cycle(cycle의 간선 합계가 음수)이 있는 그래프에서는 사용할 수 없다.

코드 예시

class FloydWarshall {
 
    public static int[][] edge;
    public static int[][] floydWarshall;
 
    public static void main(String[] args) {
        int vertex = 7;
        edge = new int[vertex+1][vertex+1];
        floydWarshall = new int[vertex+1][vertex+1];
        int[][] inputEdge = {{1, 2, 3}, {1, 5, 2}, {5, 3, 5}, {3, 4, 7}, {3, 6, 3}, {3, 7, 8}, {2, 7, 2}};
        for(int i=0; i<inputEdge.length; i++) {
            edge[inputEdge[i][0]][inputEdge[i][1]] = inputEdge[i][2];
            edge[inputEdge[i][1]][inputEdge[i][0]] = inputEdge[i][2];
        }
        for(int i=1; i<floydWarshall.length; i++) {
            for(int j=1; j<floydWarshall[i].length; j++) {
                if(i==j) floydWarshall[i][j] = 0;
                else {
                    if(inputEdge[i][j]==0) floydWarshall[i][j] = Integer.MAX_VALUE>>1;
                    else floydWarshall[i][j] = edge[i][j];
                }
            }
        }
        for(int k=1; k<=vertex; k++) {
            for(int i=1; i<floydWarshall.length; i++) {
                for(int j=1; j<floydWarshall[i].length; j++) {
                    if(floydWarshall[i][j]>floydWarshall[i][k]+floydWarshall[k][j]) floydWarshall[i][j]=floydWarshall[i][k]+floydWarshall[k][j];
                }
            }    
        }
        for(int i=1; i<floydWarshall.length; i++) {
            for(int j=1; j<floydWarshall[i].length; j++) {
                System.out.print(floydWarshall[i][j]+" ");
            }
            System.out.println();
        }
    }
}

관련 문제

developmentspace.tistory.com/98?category=737181

[프로그래머스] 합승 택시 요금