Floyd Warshall

The Floyd Warshall algorithm is used to find the shortest path between all vertices in the weighted graph. This algorithm works with both directed and undirected graphs but it does not work along with the graph with negative cycles. Therefore, if the distance from the vertex v from itself is negative then we can assume that the graph has the presence of a negative cycle. This algorithm follows the dynamic programming approach as its working pattern. Here the algorithm doesn’t construct the path itself but it can reconstruct the path with a simple modification. Floyd Warshall algorithm is also known as Roy Warshall algorithm or Roy-Floyd algorithm. Let us study the working of the Floyd Warshall algorithm.

Algorithm
We construct a matrix D that gives the length of the shortest path between each pair of nodes.
The algorithm initializes D to L, that is, to the direct distances between nodes. It then does n iterations, after iteration k, D gives the length of the shortest paths that only use nodes in {1,2….k} as intermediate nodes.
After n iterations, D, therefore, gives the length of shortest paths using any of the nodes in N as an intermediate node. If Dk represents the matrix D after kth iteration it can be implemented by
Dk [i , j] = min (Dk-1 [i , j], Dk-1 [i, k] + Dk-1 [k , j])
We use the principle of optimality to compute length from i to j passing through k.

#datastructures #algorithm #floydwarshall

Follow Me On Social Media