Floyd-Warshall Algorithm – All Pairs Shortest Paths

Floyd-Warshall Algorithm – All Pairs Shortest Paths

Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles.

Algorithm:

FLOYD - WARSHALL (W)

 1. n ← rows [W].

 2. D⁰ ← W

 3. for k ← 1 to n

 4. do for i ← 1 to n    

 5. do for j ← 1 to n    

 6. do d_ij^(k) ← min (d_ij^(k-1),d_ik^(k-1)+d_kj^(k-1) )

 7. return D⁽ⁿ⁾

Example:

Consider the above graph, to find all pairs shortest path build a n x n matrix. Here n is 4, therefore take a 4x4 matrix.

Initialize the weights to 0 to same nodes and all corresponding node weights.

Now for the three loop variables k,i,j iterate

In the above figure the rounded values are updated values in the loop iterations of k, i, j.

And the matrix gives all pairs shortest paths.