Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

general
communitycreator

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.

123410852230999999993999920999947999910
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]}

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

=>A1A^{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.

1234108522308839999209999471510
Intermediate matrix A power 1

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

1234108522308535207471510
Intermediate matrix A power 2

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

123410752230853520746310
Intermediate matrix A power 3

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

123410532230653520746310
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).

RELATED TAGS

general
communitycreator

CONTRIBUTOR

Pranavi Anoushka Tirumalasetty
RELATED COURSES

View all Courses

Keep Exploring