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 pairs shortest paths rather than finding the shortest path from one node to all others 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(n3). Where is a number of nodes/vertices in the graph.

## 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

``````#include <bits/stdc++.h>
#define INF 666
using namespace std;

int main() {
int n, m;
cin >> n >> m;

// Initializing matrix with infinty
int matrix[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j)
matrix[i][j] = 0;  // distance of node from itself.
else
matrix[i][j] = INF;
}
}

// taking input directly in the resultant matrix.
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
matrix[u][v] = w;
}

// floyd warshall algorithm
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%5d ", matrix[i][j]);
}
cout << "\n";
}

return 0;
}``````

Input:

``````6 9
1 5 2
1 4 2
5 4 3
5 6 4
4 6 1
4 3 6
2 3 4
4 2 6
2 1 5``````

Output:

``````    0     8     8     2     2     3
5     0     4     7     7     8
666   666     0   666   666   666
11     6     6     0    13     1
14     9     9     3     0     4
666   666   666   666   666     0``````

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

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