플루이드 와샬 최단거리 알고리즘

플루이드 와샬 알고리즘

GeeksforGeeks의 Floyd Warshall Algorithm | DP-16를 번역한 글입니다.

플루이드 와샬은 모든 쌍의 최단거리를 구하는 문제이다. 주어진 가중치가 있는 방향 간선에서 모든 정점 사이의 최단거리를 해결하는 문제이다.

첫번째로 그래프 메트릭스와 같은 솔루션 메트릭스를 초기화 한다. 그 다음 모든 정점을 중간 정점으로 고려하면서 솔루션 메트릭스를 갱신할 것이다. 이 알고리즘의 아이디어는 모든 정점을 하나하나 선택하여 모든 최단거리를 갱신하는 것인데, 선택된 정점을 중간 정점으로 포함하는 것이다. 정점 K를 중간 정점으로 선택한다면, 이미 {1,2,3, ... k-1}의 정점들은 중간 정점으로 구려된 후이다. 모든 정점의 쌍 (i, j)을 시작점과 끝점으로 여긴다면, 두가지 가능성이 있다.

1) K는 최단거리 (i, j)의 중간 정점이 아니기 때문에 dist'[i][j]'를 그대로 유지한다. (dist 배열은 솔루션 메트릭스이다.)

2) K가 최단거리 (i, j)의 중간 정점에 포함된다. 때문에 만얃ㄱ dist[i][j]의 값이 dist[i][k] + dist[k][j] 값보다 크다면 dist[i][j]의 값을 dist[i][k] + dist[k][j] 로 갱신해야한다.

다음의 그림은 위의 설명을 보여준다.

class AllPairShortestPath 
{ 
    final static int INF = 99999, V = 4; 
  
    void floydWarshall(int graph[][]) 
    { 
        int dist[][] = new int[V][V]; 
        int i, j, k; 
  
        /* Initialize the solution matrix same as input graph matrix. 
           Or we can say the initial values of shortest distances 
           are based on shortest paths considering no intermediate 
           vertex. */
        for (i = 0; i < V; i++) 
            for (j = 0; j < V; j++) 
                dist[i][j] = graph[i][j]; 
  
        /* Add all vertices one by one to the set of intermediate 
           vertices. 
          ---> Before start of an iteration, we have shortest 
               distances between all pairs of vertices such that 
               the shortest distances consider only the vertices in 
               set {0, 1, 2, .. k-1} as intermediate vertices. 
          ----> After the end of an iteration, vertex no. k is added 
                to the set of intermediate vertices and the set 
                becomes {0, 1, 2, .. k} */
        for (k = 0; k < V; k++) 
        { 
            // Pick all vertices as source one by one 
            for (i = 0; i < V; i++) 
            { 
                // Pick all vertices as destination for the 
                // above picked source 
                for (j = 0; j < V; j++) 
                { 
                    // If vertex k is on the shortest path from 
                    // i to j, then update the value of dist[i][j] 
                    if (dist[i][k] + dist[k][j] < dist[i][j]) 
                        dist[i][j] = dist[i][k] + dist[k][j]; 
                } 
            } 
        } 
    } 
}

특징

• DP 문제 중 하나이다.

• 3중 포문으로 문제를 해결해야하기 때문에 시간복잡도는 O(V^3)이다. 때문에 정점의 개수가 많다면 다익스트라의 최단거리 알고리즘을 여러번 사용하여 문제를 해결하는 것이 좋다.

• 다익스트라보다 시간이 많이 걸리지만 한번에 모든 정점의 최단거리를 구할 수 있는 장점이 있다.

• 문제에 따라 무방향그래프를 활용할 수도 있으며, 초기값 설정, 자기 자신( i == j )의 초기값 등을 잘 생각해야한다.