Floyd Warshall’s All Pair Shortest Path Algorithm from Dynamic Programming Perspective.

Input: Given a weighted graph G with vertex set V and Edges E.

V represents the set of all vertices, E is a collection of pairs (i,j) representing an edge from i to j

Problem: Find the weight of the shortest path for all possible pair of vertices.

If we are having a graph with vertices V = {1,2,3….,n}.

If sp(i,j,k) = weight of the shortest path from vertex i to vertex j which can have vertices 1,2,3…k as intermediate nodes in that shortest path.

Then the final solution of the shortest path from vertex i to vertex j would be sp(i,j,n) that is weight of the shortest path from vertex i to vertex j which can have any vertex (1,2,3…n) as intermediate nodes.

We need to find sp(i,j,n) for all i∈V, j∈V, where n=|V|=number of vertices

For example if our graph is:

Sample graph

Then sp(1,3,2) = weight of the shortest path from vertex 1 to vertex 3 which can have vertices 1,2 as intermediate vertex. sp(1,3,2) = 7

sp(1,3,4)=4 , sp(1,3,5)=4

sp(1,3,0)=infinity as no intermediate vertex is allowed and vertex 1 , vertex 3 are not directly connected,

sp(1,3,1)=infinity, sp(1,3,2)=7, sp(1,3,3)=7, sp(1,3,4)=4, sp(1,3,5)=4

Optimal Substructure property

sp(i,j,k) = shortest path from vertex i to vertex j which can have vertices 1,2,3,4…k as intermediate vertices .

sp(i,j,k) can be expressed in terms of subproblems as

Optimal Substructure Property

Case: If the shortest path from vertex i to vertex j passes through vertex k. Then sp(i,j,k) = shortest path from vertex i to vertex k using vertices 1,2,3,4…k-1 as intermediate vertices + shortest path from vertex k to vertex j using vertices 1,2,3,… k-1 as intermediate vertices.

Solution Time

Let’s take a graph and try to find the shortest path between all pair of vertices in a bottom up manner, that is initially we try to find the shortest path from vertex i to vertex j having only direct edges. Then we try to find the shortest path from vertex i to vertex j which can have vertex 1 as intermediate vertex. Then we try to find the shortest path from vertex i to vertex j which can have vertex 1 and vertex 2 as intermediate vertices. So on…. The final answer would be sp(i,j,|V|) for all i∈V, j∈V

|V| denotes the total number of vertices.

Let’s start with the base case, that is the shortest path between any two vertices having no intermediate vertex and only direct edges. So, sp(i,j,0) for all i∈V, j∈V will look like this:

This matrix sp[i][j] is denoting the shortest path from vertex i to vertex j having no intermediate vertex in between and only direct edges.

Blank cells in the matrix denotes the value INFINITY

Now lets try to find out sp(i,j,1) for all i∈V, j∈V, that is the shortest path between all pair of vertices which can have only vertex 1 as intermediate node.

for all i∈V, j∈V, sp(i,j,1) = min( (sp(i,1,0)+sp(1,j,0)) OR sp(i,j,0) )

sp(5,2,1) = min((sp(5,1,0) + sp(1,2,0) ) OR sp(5,2,0))
          = min( (3 + 2) OR (INFINITY) ) 
          = 5

sp(5,4,1) = min((sp(5,1,0) + sp(1,4,0) ) OR sp(5,4,0))
          = min( (3 + 7) OR (INFINITY) ) 
          = 10

Vertex 1 can be intermediate vertex.

Now lets try to find out sp(i,j,2) for all i∈V, j∈V, that is the shortest path between all pair of vertices which can have vertex 1, vertex 2 as intermediate node.

for all i∈V, j∈V, sp(i,j,2) = min( (sp(i,2,1)+sp(2,j,1)) OR sp(i,j,1) )

sp(1,3,2) = min((sp(1,2,1) + sp(2,3,1) ) OR sp(1,3,1))
          = min( (2 + 2) OR (INFINITY) ) 
          = 5

sp(1,4,2) = min( (sp(1,2,1) + sp(2,4,1)) OR sp(1,4,1) ) 
          = min( (2+ 4) OR 7) 
          = 6
so on....

Vertex 1 and vertex 2 can serve as intermediate vertices

Now lets try to find out sp(i,j,3) for all i∈V, j∈V, that is the shortest path between all pair of vertices which can have vertex 1, vertex 2, vertex 3 as intermediate nodes.

for all i∈V, j∈V, sp(i,j,3) = min( (sp(i,3,2)+sp(3,j,2)) OR sp(i,j,2) )

Vertices 1,2 and 3 can serve as intermediate vertices

Now lets try to find out sp(i,j,4) for all i∈V, j∈V, that is the shortest path between all pair of vertices which can have vertex 1, vertex 2, vertex 3 and vertex 4 as intermediate nodes.

for all i∈V, j∈V, sp(i,j,4) = min( (sp(i,4,3)+sp(4,j,3)) OR sp(i,j,3) )

As there are no outgoing edges from vertex 4, so no update in the shortest path matrix

Now lets try to find out sp(i,j,5) for all i∈V, j∈V, that is the shortest path between all pair of vertices which can have vertices 1, 2, 3, 4, 5 as intermediate nodes.

for all i∈V, j∈V, sp(i,j,5) = min( (sp(i,5,4)+sp(5,j,4)) OR sp(i,j,4) )

Vertices 1,2,3,4,5 can serve as intermediate vertices

PsuedoCode:

If the graph is represented using adjacency matrix.

allocate memory to sp matrix of size |V|*|V|*|V|
//Base case, shortest path consisting of only direct edges
for(vertices i =1 to |V|)
{
    for(vertices j =1 to |V|)
    {
       sp[i,j,0] = graph[i,j] // graph is represented using adj matrix
    }
}

for(intermediate vertex k=1 to |V|)
{
    for(vertices i=1 to |V|)
    {
         for(vertices j=1 to |V|)
         {
             sp[i,j,k]=min((sp[i,k,k-1] + sp[k,j,k-1]),sp[i,j,k-1])
         }
    }
}

Time Complexity:

The time complexity of the pseudocode discussed above is O(|V|³).

Space Complexity:

The space complexity of the pseudocode discussed above is O(|V|³), but as while computing sp[i,j,k] we are only using the results of sp[i,j,k-1], therefore we can optimize the space complexity to O(|V|²), so that sp matrix only stores the result of last iteration (k-1)

The optimized pseudocode would be:

allocate memory to sp matrix of size |V|*|V|
//Base case, shortest path consisting of only direct edges
for(vertices i =1 to |V|)
{
    for(vertices j =1 to |V|)
    {
       sp[i,j] = graph[i,j] // graph is represented using adj matrix
}
}
for(intermediate vertex k=1 to |V|)
{
    for(vertices i=1 to |V|)
    {
         for(vertices j=1 to |V|)
         {
             sp[i,j] = min((sp[i,k] + sp[k,j]),sp[i,j])
         }
}
}