Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags


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

Pranavi Anoushka Tirumalasetty

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:

We have to find the shortest path from every vertex to all other vertices

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 A0A^{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.

Adjacency matrix A power 0
  • Now, we prepare the A1A^{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 A1A^{1} matrix, the first row and first column remain the same as matrix A0A^{0}.
  • After that, we take any two vertices and compare the edge length using the formula:

AkA^{k}[i,j] = min{Ak1A^{k-1}[i,j] , Ak1A^{k-1}[i,k]+Ak1A^{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:

A1A^{1}[2,3]=min{A0A^{0}[2,3] , A0A^{0}[2,1]+A0A^{0}[1,3]}

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

=> A1A^{1}[2,3] = 2

Similarly, A1A^{1}[3,2]=min{A0A^{0}[3,2] , A0A^{0}[3,1]+A0A^{0}[1,2]}



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

Intermediate matrix A power 1

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

Intermediate matrix A power 2

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

Intermediate matrix A power 3

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

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




Pranavi Anoushka Tirumalasetty

View all Courses

Keep Exploring