Test yourself
Consider the following graph..
The length of the shortest path from vertex 1 to vertex 2, 3, 4 respectively would be
If the number of vertices is 5, how many times will we have to check if a shorter path is available ?
The Floyd Warshall algorithm is used to find the shortest path between any pair of vertices in a directed graph.
1) Create a double dimensional V*V array to help you store the distances between every pair of vertices.
2) The distances from a point to itself will be zero, so the values along the diagonal can be set to zero. For all the vertices with a direct edge between them, their distance can be set to the value of the edge weight. Else, initialize the distance between the points to infinity.
3) Now for each trio of vertices i, j, and k, there are two possibilities-
- The point k is a part of the shortest path between i and j
- The point k is not present in the shorest path between i and j
4) So if the value of dist[i][k] + dist[k][j] < dist[i][j], ie. the path between i and j going through k is shorter and better than the current path, then the value of dist[i]ij] can be updated to the smaller value.
5) For each value of k, we go through every value of i and j, and at the end of these iterations, have the shortest path between all pairs stored in the array.