Floyd Warshall

출처 : https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/

Graph 알고리즘 중 하나인 Floyd Warshall 알고리즘에 대해 알아보려고 한다.

Floyd Warshall 알고리즘은 가중치 있는 그래프에서 각 정점간의 페어 중 가장 짧은 길이를 찾는 알고리즘이다. 그렇다고 친절하게 가장 짧은 정점을 알려주는 것은 아니고 아래의 예시에서 볼 수 있듯이, 정점과 정점간의 가장 짧은 길이만 계산한다.

Input:
       graph[][] = { {0,   5,  INF, 10},
                    {INF,  0,  3,  INF},
                    {INF, INF, 0,   1},
                    {INF, INF, INF, 0} }
which represents the following graph
             10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3       
Note that the value of graph[i][j] is 0 if i is equal to j 
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.

Output:
Shortest distance matrix
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0 

알고리즘의 동작 과정을 살펴보면, 

k를 i와 j 사이의 중간 정점(즉, i에서 j로 갈 때 k를 거쳐야 가장 빠름)으로 간주한다. 그래서 모든 pair(i, j)에 대해 k의 모든 값을 하나씩 넣어보면서 pair(i, j)에 가장 낮은 값(가장 낮은 값이 가장 짧은 길이이기 때문)을 찾는다.

결과적으로 간략히 과정은 다음과 같다.

1) k를 고려하지 않고 pair(i, j) 값을 유지한다. (물론 해당 pair 값이 가장 짧은 거리 일 수도 있다.

2) k를 고려하고 dist[i][j] as dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j] 와 같이 계산한다.

이를 바탕으로 실제 코드를 살펴보면

// Solves the all-pairs shortest path problem using Floyd Warshall algorithm void floydWarshall (int graph[][V]) {     /* dist[][] will be the output matrix that will finally have the shortest        distances between every pair of vertices */     int dist[V][V], 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];             }         }     }        // Print the shortest distance matrix     printSolution(dist); }

코드를 보면 알 수 있듯이 의외로 간단하다.

대신 반복문의 중첩이 3개이기 때문에 시간 복잡도가 O^3 이다. 때문에 정점이 많으면 많을수록 메모리 점유율도 많아지고 (테이블을 통채로 저장하기 때문에) 코드 수행 시간도 많이 늘어난다.