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 cannot 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).

Find the shortest paths between all pairs of vertices in the graph G. A classic application of this problem is computing distances between all pairs of cities in a map.

Optimal Substructure

Let us consider a subset k {1, 2, 3,….k} of vertices V, 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 (p_ij) 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

Example

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}};

    
    cout<<"Graph G (Adjacency Matrix):"<<endl;
    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(n³)
Space complexity: O(n²), (n is the number of vertices in the graph)

Here’s a working example: Floyd-Warshall Algorithm

Reference:
Introduction to Algorithms