Finding all pair Shortest Path in Graph using Floyd-Warshall Algorithm

Things to be discussed here.

• Floyd-Warshall Algorithm
• Practice Problem

Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm provides a Dynamic Programming based approach for finding the Shortest Path. This algorithm finds all pair shortest paths rather than finding the shortest path from one node to all other as we have seen in the Bellman-Ford and Dijkstra Algorithm.

• The edge weight can be both negative or positive.
• The running time of this algorithm is O(n³). Where n is a number of nodes/vertices in the graph.
• Explanation video from YouTube

Implementation for the optimal path:

• Initialize 2D array of size N*N with INF as the initial distance between pair of vertices.
• Find all pair shortest distance which uses 0 intermediate nodes ( meaning these nodes are connected with direct edges ) and update the value.
• Then find all pair shortest distance which uses 1 intermediate node ( i.e. if you have to go from u to v then use path u -> k and k -> v ).
• and so own until you use all N nodes as intermediate nodes.
• For any two vertices (i,j), one could minimize the distance between pair (i,j) by using first k nodes as intermediate nodes. So the shortest distance will be.
• min( dist[i][j], dist[i][k]+dist[k][j] )
• In the end, this will give you the final optimal distance between two vertices.
• For negative cycle detection, we can use the observation that distance of any node from itself is 0 but due to the presence of a negative cycle it will become negative.
• In the implementation, we have used node number from 1,2, . . . , N.
• C++ Implementation

Extended implementation to find the shortest distance using k intermediate nodes. When we take k=N then we will get the optimal solution as above.

• To implement this we will be using a 3D array of size N*N*N (as DP[N][N][N] )with INF as the initial distance between pair of vertices.
• Store the graph in the Adjacency Matrix, let us say M[N][N].
• Algorithm

for(int k=0; k<n; k++){     for(int i=0; i<n; i++) {         for(int j=0; j<n; j++) {             if(k==0) DP[k][i][j] = M[i][j];             else DP[k][i][j] = min( DP[k-1][i][j], DP[k-1][i][k] + DP[k-1][k][j] );        }     } }

Applications: 

• Detecting the presence of the negative cycle.
• Finding the shortest path in the directed graph.

Practice Problem

1. Arbitrage ( UVA )
2. Commandos ( UVA )
3. Greg and Graph ( 295B )
4. Road Construction ( UVA )

That's all for this article, in the next session we will be discussing Minimum Spanning Tree and Kruskal's Algorithm and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA