All Pairs Shortest Path Algorithm – Introduction

All Pairs Shortest Path Algorithm is also known as the Floyd-Warshall algorithm. And this is an optimization problem that can be solved using dynamic programming.

Let G = <V, E> be a directed graph, where V is a set of vertices and E is a set of edges with nonnegative length. Find the shortest path between each pair of nodes.

L = Matrix, which gives the length of each edge

L[i, j] =   0, if i == j // Distance of node from itself is zero

L[i, j] =  ∞ , if i ≠ j and (i, j) ∉ E

L[i, j] = w (i, j), if i ≠ j and (i, j) ∈ E  // w(i, j) is the weight of the edge (i, j)

Principle of optimality :

If k is the node on the shortest path from i to j, then the path from i to k and k to j, must also be shortest.

In the following figure, the optimal path from i to j is either p or summation of p1 and p2.

All Pairs Shortest Path

While considering kth vertex as intermediate vertex, there are two possibilities :

  • If k is not part of shortest path from i to j, we keep the distance D[i, j] as it is.
  • If k is part of shortest path from i to j, update distance D[i, j] as
    D[i, k] + D[k, j].

Optimal sub structure of the problem is given as :

Dk [i, j] = min{ Dk – 1 [i, j], Dk – 1 [i, k] + Dk – 1 [k, j] }

Dk = Distance matrix after kth iteration

Algorithm for All Pairs Shortest Path

This approach is also known as the Floyd-warshall shortest path algorithm. The algorithm for all pair shortest path (APSP) problem is described below

Algorithm FLOYD_APSP ( L)
// L is the matrix of size n  n representing original graph
// D is the distance matrix

D ← L
for  k ← 1 to n do
  for  i ←1 to n do
    for j ← 1 to n do
      D[i, j]k ← min ( D[i, j]k-1, D[i, k]k-1 + D[k, j]k-1 )
    end
  end
end
return D

Complexity analysis of All Pairs Shortest Path Algorithm

It is very simple to derive the complexity of all pairs’ shortest path problem from the above algorithm. It uses three nested loops. The innermost loop has only one statement. The complexity of that statement is Q(1).

The running time of the algorithm is computed as :

Example

Problem: Apply Floyd’s method to find the shortest path for the below-mentioned all pairs.

All Pairs Shortest Path example

Solution:

Optimal substructure formula for Floyd’s algorithm,                                

Dk [i, j] = min { Dk – 1 [i, j], Dk – 1 [i, k] + Dk – 1 [k, j] }

All Pairs Shortest Path solution

Iteration 1 : k = 1 :

D1[1, 2] = min { Do [1, 2], Do [1, 1] + Do [1, 2] }

= min {∞, 0 + ∞} 

=  ∞

D1[1, 3] = min { Do [1, 3], Do [1, 1] + Do [1, 3] }

= min {3, 0 + 3} 

= 3

D1[1, 4] = min { Do [1, 4], Do [1, 1] + Do [1, 4] }

= min {∞, 0 + ∞} 

=  ∞

D1[2, 1] = min { Do [2, 1], Do [2, 1] + Do [1, 1] }

= min {2, 2 + 0} 

= 2

D1[2, 3] = min { Do [2, 3], Do [2, 1] + Do [1, 3] }

= min {∞, 2 + 3} 

= 5

D1[2, 4] = min { Do [2, 4], Do [2, 1] + Do [1, 4] }

= min {∞, 2 + ∞} 

= ∞

D1[3, 1] = min { Do [3, 1], Do [3, 1] + Do [1, 1] }

= min {∞, 0 + ∞} 

= ∞

D1[3, 2] = min { Do [3, 2], Do [3, 1] + Do [1, 2] }

= min {7, ∞ + ∞} 

= 7

D1[3, 4] = min { Do [3, 4], Do [3, 1] + Do [1, 4] }

= min {1, ∞ + ∞} 

= 1

D1[4, 1] = min { Do [4, 1], Do [4, 1] + Do [1, 1] }

= min {6, 6 + 0} 

= 6

D1[4, 2] = min { Do [4, 2], Do [4, 1] + Do [1, 2] }

= min {∞, 6 + ∞} 

= ∞

D1[4, 3] = min { Do [4, 3], Do [4, 1] + Do [1, 3] }

= min {∞, 6 + 3} 

= 9

All Pairs Shortest Path problem

Note : Path distance for highlighted cell is improvement over original matrix.

Iteration 2 (k = 2) :

D2[1, 2] = D1 [1, 2]  =  ∞

D2[1, 3] = min { D1 [1, 3], D1 [1, 2] + D1 [2, 3] }

= min {3, ∞ + 5} 

= 3

D2[1, 4] = min { D1 [1, 4], D1 [1, 2] + D1 [2, 4] }

= min {∞, ∞ + ∞} 

= ∞

D2[2, 1] = D1 [2, 1]  =  2

D2[2, 3] = D1 [2, 3]  =  5

D2[2, 4] = D1 [2, 4]  =  ∞

D2[3, 1] = min { D1 [3, 1], D1 [3, 2] + D1 [2, 1] }

= min {∞, 7 + 2} 

= 9

D2[3, 2] = D1 [3, 2]  =  7

D2[3, 4] = min { D1 [3, 4], D1 [3, 2] + D1 [2, 4] }

= min {1, 7 + ∞} 

= 1

D2[4, 1] = min { D1 [4, 1], D1 [4, 2] + D1 [2, 1] }

= min {6, ∞ + 2} 

= 6

D2[4, 2] = D1 [4, 2]  =  ∞                                

D2[4, 3]  =  min { D1 [4, 3], D1 [4, 2] + D1 [2, 3] }

= min {9, ∞ + 5} 

= 9

Iteration 3 (k = 3) :

D3[1, 2] = min { D2 [1, 2], D2 [1, 3] + D2 [3, 2] }

= min {∞, 3 + 7} 

= 10

D3[1, 3] = D2 [1, 3]  =  3

D3[1, 4] = min { D2 [1, 4], D2 [1, 3] + D2 [3, 4] }

= min {∞, 3 + 1} 

= 4

D3[2, 1] = min { D2 [2, 1], D2 [2, 3] + D2 [3, 1] }

= min {2, 5 + 9} 

= 2

D3[2, 3] = D2 [2, 3]  =  5

D3[2, 4] = min { D2 [2, 4], D2 [2, 3] + D2 [3, 4] }

= min {∞, 5 + 1} 

= 6

D3[3, 1] = D2 [3, 1]  =  9

D3[3, 2] = D2 [3, 2]  =  7

D3[3, 4] = D2 [3, 4]  =  1

D3[4, 1] = min { D2 [4, 1], D2 [4, 3] + D2 [3, 1] }

= min {6, 9 + 9} 

= 6

D3[4, 2] = min { D2 [4, 1], D2 [4, 3] + D2 [3, 2] }

= min {∞, 9 + 7} 

= 16

D3[4, 3] = D2 [4, 3]  =  9

Iteration 4 (k = 4) :

D4[1, 2] = min { D3 [1, 2], D3 [1, 4] + D3 [4, 2] }

= min {10, 4 + 16} 

= 10

D4[1, 3] = min { D3 [1, 3], D3 [1, 4] + D3 [4, 1] }

= min {3, 4 + 9} 

= 3

D4[1, 4] = D3 [1, 4]  =  4

D4[2, 1] = min { D3 [2, 1], D3 [2, 4] + D3 [4, 1] }

= min {2, 6 + 6} 

= 2

D4[2, 3] = min { D3 [2, 3], D3 [2, 4] + D3 [4, 3] }

= min {5, 6 + 9} 

= 5

D4[2, 4] = D3 [2, 4]  =  6

D4[3, 1] = min { D3 [3, 1], D3 [3, 4] + D3 [4, 1] }

= min {9, 1 + 6} 

= 7

D4[3, 2] = min { D3 [3, 2], D3 [3, 4] + D3 [4, 2] }

= min {7, 1 + 16} 

= 7

D4[3, 4] = D3 [3, 4]  =  1

D4[4, 1] = D3 [4, 1]  =  6

D4[4, 2] = D3 [4, 2]  = 16

D4[4, 3] = D3 [4, 3]  =  9

Final distance matrix is,

All Pairs Shortest Path

Problem: Obtain all pair shortest path using Floyd’s Algorithm for given weighted graph

Example of All Pairs Shortest Path

Solution:

Optimal substructure formula for Floyd’s algorithm,

Dk [i,j] = min{ Dk – 1 [i, j], Dk – 1 [i, k] + Dk – 1 [k, j] }

Iteration 1 (k = 1) :

D1 [1, 2] = min {D0[1, 2], D0[1, 1] + D0[1, 2] }

= min {8, 0 + 8}

= 8

D1[1, 3] = min {D0[1, 3], D0[1, 1] + D0[1, 3] }

= min {5, 0 + 5}

= 5

D1[2, 1] = min {D0[2, 1], D0[2, 1] + D0[1, 1] }

= min {2, 2 + 0}

= 2

D1[2, 3] = min {D0[2, 3], D0[2, 1] + D0[1, 3] }

= min {∞, 2 + 5}

= 7

D1[3, 1] = min {D0[3, 1], D0[3, 1] + D0[1, 1] }

= min {∞, ∞ + 0}

= ∞

D1[3, 2] = min {D0[3, 2], D0[3, 1] + D0[1, 2] }

= min {1, 1 + 8}

= 1

Iteration 2 (k = 2) :

D2[1, 2] = min {D1[1, 2],  D1[1, 2] + D1[2, 2]}

= min {8, 8 + 0}

= 8

D2[1, 3] = min {D1[1, 3], D1[1, 2] +  D1[2, 3] }

= min {5, 8 +7}

= 5

D2[2, 1] = min {D1[2, 1], D1[2, 2] + D1[2, 1}

=  min {2, 0 + 2}

= 2

D2[2, 3] = min {D1[2, 3], D1[2, 2] + D1[2, 3] }

=  min {7, 0 + 7}

= 7

D2[3, 1] = min {D1[3, 1], D1[3, 2] + D1[2, 1] }

= min {∞, 1 + 2}

= 3

D2[3, 2] = min {D1[3, 2], D1[3, 2] + D1[2, 2] }

= min {1, 1 + 0}

= 1

Iteration 3 (k = 3) :

D3[1, 2] = min {D2[1, 2],  D2[1, 3] + D2[3, 2]}

= min {8, 5 + 1}

= 6

D3[1, 3] = min {D2[1, 3], D2[1, 3] +  D2[3, 3] }

= min {5, 5 + 0}

= 5

D3[2, 1] = min {D2[2, 1], D2[2, 3] + D2[3, 1}

= min {2, 7 + 3}

= 2

D3[2, 3] = min {D2[2, 3], D2[2, 3] + D2[3, 3] }

= min {7, 7 + 0}

= 7

D3[3, 1] = min {D2[3, 1], D2[3, 3] + D2[3, 1] }

= min {3, 0 + 3}

= 3

D3[3, 2] = min {D2[3, 2], D2[3, 3] + D2[3, 2] }

= min {1, 0 + 1}

= 1


Additional Reading: Fast Implementation