How to find minimum cost path in all-pairs shortest path problem

What is the all-pairs shortest path problem?

For a directed weighted graph (G) with (V) vertices and (E) edges, we have to find the shortest path possible from every vertex to all other remaining vertices. To find this shortest path, we will use the following technique known as the Floyd- Warshall technique.

Let’s look at the following example for a clearer explanation:

In the above example, we have to find shortest path from vertex 1 to vertices 2,3,4, from vertex 2 to vertices 1,3,4, and so on for every vertex.

While generating the shortest path for any two vertices, they may both have a shortest direct path, or there might be an intermediate vertex through which the path becomes shortest.

• First, we write the adjacency matrix $A^{0}$ for the given graph, where rows and columns are vertices and the direct edge length between these vertices are set as values in the matrix.

• If there is no direct edge between any two vertices, then we will fill that using the biggest 4 digit number (9999) as an indication of infinity. The diagonal elements will remain 0 because there is no self loop.

• Now, we prepare the $A^{1}$ matrix, considering intermediate vertex as vertex 1. We then check to see if there is a better shortest path going via vertex 1 – we will then continue to do the same with all four vertices.

How to write matrices using intermediate vertex

• When we use any vertex as an intermediate vertex while preparing that matrix, all the paths that belong to that vertex remain unchanged, i.e., for $A^{1}$ matrix, the first row and first column remain the same as matrix $A^{0}$.
• After that, we take any two vertices and compare the edge length using the formula:

$A^{k}$[i,j] = min{$A^{k-1}$[i,j] , $A^{k-1}$[i,k]+$A^{k-1}$[k,j]}

Note: to generate the matrix with intermediate value k we always use its previous matrix with intermediate value k-1.

For example:

$A^{1}$[2,3]=min{$A^{0}$[2,3] , $A^{0}$[2,1]+$A^{0}$[1,3]}

=> $A^{1}$[2,3]=min{2 ,8+9999}

=> $A^{1}$[2,3] = 2

Similarly, $A^{1}$[3,2]=min{$A^{0}$[3,2] , $A^{0}$[3,1]+$A^{0}$[1,2]}

=>$A^{1}$[3,2]=min{9999,5+3}

=>$A^{1}$[3,2]=8

In this manner we form the intermediate matrices for all four vertices and fill the minimum possible values using the formula.

Now, we write intermediate matrix using vertex 2, i.e., $A^{2}$.

Next, we write intermediate matrix using vertex 3, i.e., $A^{3}$.

Now, we write the intermediate matrix using vertex 4, i.e., $A^{4}$.

• Therefore, through using this Floyd-Warshall technique we can compute the minimum path cost between the vertices.
• The final matrix, $A^{4}$, contains the shortest minimum path cost between the vertices of the graph (G).