All Pairs Shortest Path Problem | Floyd Warshall Algorithm

All Pairs Shortest Path Problem

1. Let G be a directed graph with n vertices and cost be its adjacency matrix
2. The problem is to determine a matrix A such that A(i,j) is the length of a shortest path from i^th vertex to j^th vertex
3. This problem is equivalent to solving n single source shortest path problems using greedy method
4. Robert Floyd developed a solution using dynamic programming method
5. A shortest path from I to j goes through 0 or more intermediate vertices and terminates at j
6. If k is an intermediate vertex on this shortest path, then the sub paths from i to k and from k to j must be shortest paths from i to k and k to j respectively. This is based on the principle of optimality.
7. The solution matrix is obtained iteration wise by computing A_0, A_1, A_2, … A_n
   A₀ is the cost matrix. The next iterations give the matrix A_k which is computed as follows:
   A^k(i, j) = min{ A^k-1(i, j), A^k-1(i,k) + A^k-1(k, j) }, k >= 1
8. An algorithm for the all-pairs shortest path problem is given below:

   Algorithm AllPaths(cost, A, n)
    // cost[1:n][1:n] is the cost adjacency matrix of a graph with n vertices;
    // A[i][j] is the cost of a shortest path from vertex i to vertex j.
    // cost[i][i] = 0.0, for 1 <= i <= n. 
    {
        for ( i:=1 to n ) do
         {
           for ( j:=1 to n ) do
             {
                A[i][j] := cost[i][j]; // Copy cost into A.
             }
         }
        for ( k:=1 to n ) do
         {
           for ( i:=1 to n ) do
            {
              for ( j:=1 to n ) do
               {
                 A[i][j] = min(A[i][j], A[i][k]+A[k][j]);
                }
            }
          }
     }
   

9. Time complexity of Floyd Warshall Algorithm is O(n³)

Topic : All Pairs Shortest Path Problem | Floyd Warshall Algorithm