Floyd-Warshall Algorithm Implementation | All pairs shortest path

Floyd-Warshall algorithm helps in finding the shortest path between all pairs of vertices in a graph. The problem of all-pairs shortest path can be solved by running a single source shortest path algorithm like Dijkstra’s algorithm, |V| (notation for no. of vertices) times.
However, if a graph has negative weight edges, we couldn’t use Dijkstra’s algorithm to find the all-pairs shortest path. So to find the all-pairs shortest path for a graph with negative weights we use Floyd-Warshall algorithm. However, it also couldn’t be used with a graph having a negative-cycle, otherwise we would keep moving in the cycle with negative weights (-∞).

Problem statement

Given an adjacency-matrix for a graph G, such that:

G[i][j] = ∞, if there’s a no edge between vertices i and j,
and G[i][j] = w, otherwise, representing the edge’s weight (w) between i and j (negative weights allowed).

Optimal Substructure

Let us consider a subset of vertices V,
k (1, 2, 3,….k) for some integer k <= V.
Now for any pair of vertices i, j (in V) considering all paths from i to j using intermediary vertices selected from set k. We could find the shortest path (pij) between node i and j using intermediary vertices (k) such that,

pij(k) = wij, if k = 0 (no intermediary node)
= min (pij(k-1), pik(k-1)+ pkj(k-1)), if k > 0

Note: This problem is similar to the Matrix-chain Multiplication problem, explained step-by-step here.

Pseudocode
Floyd-Warshall (G)
n = rows[G]
P = G
for k = 1 to n:
do for i = 1 to n:
do for j = 1 to n:
pij(k) = min (pij(k-1), pik(k-1)+ pkj(k-1))

return Pn
Code Implementation
//
//  main.cpp
//  Floyd-Warshall
//
//  Created by Himanshu on 12/11/22.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#define N 5
using namespace std;

void printMatrix(int G[][N]) {

for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (G[i][j] == INT_MAX) {
cout<<"INF ";
} else {
cout<<G[i][j]<<" ";
}
}
cout<<endl;
}
}

//N = number of nodes in graph
void FloydWarshall (int P[][N]) {

for (int k=0; k<N; k++) {

for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (P[i][k] == INT_MAX || P[k][j] == INT_MAX) {
P[i][j] = P[i][j];
} else {
P[i][j] = min(P[i][j], P[i][k] + P[k][j]);
}
}
}

cout<<endl<<"Path Matrix (P) after k = "<<(k+1)<<endl;
printMatrix (P);
}

}

int main() {
int G[N][N] = {{0, 3, 8, INT_MAX, -4},
{INT_MAX, 0, INT_MAX, 1, 7},
{INT_MAX, 4, 0, INT_MAX, INT_MAX},
{2, INT_MAX, -5, 0, INT_MAX},
{INT_MAX, INT_MAX, INT_MAX, 6, 0}};

printMatrix(G);

cout<<endl<<"Floyd Warshall Algorithm:"<<endl;
FloydWarshall (G);

return 0;
}


Output

Graph G (Adjacency Matrix):
0 3 8 INF -4
INF 0 INF 1 7
INF 4 0 INF INF
2 INF -5 0 INF
INF INF INF 6 0

Floyd Warshall Algorithm:

Path Matrix (P) after k = 1
0 3 8 INF -4
INF 0 INF 1 7
INF 4 0 INF INF
2 5 -5 0 -2
INF INF INF 6 0

Path Matrix (P) after k = 2
0 3 8 4 -4
INF 0 INF 1 7
INF 4 0 5 11
2 5 -5 0 -2
INF INF INF 6 0

Path Matrix (P) after k = 3
0 3 8 4 -4
INF 0 INF 1 7
INF 4 0 5 11
2 -1 -5 0 -2
INF INF INF 6 0

Path Matrix (P) after k = 4
0 3 -1 4 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0

Path Matrix (P) after k = 5
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0 

Time complexity: O(n3)
Space complexity: O(n2), (n is the number of vertices in the graph)

Here’s a working example: Floyd-Warshall Algorithm

Reference:
Introduction to Algorithms