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.
Note: to generate the matrix with intermediate value
k
we always use its previous matrix with intermediate valuek-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}$.
RELATED TAGS
CONTRIBUTOR
View all Courses