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 (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
Example
Code Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | //// main.cpp// Floyd-Warshall//// Created by Himanshu on 12/11/22.//#include <iostream>#include <vector>#include <cmath>#include <climits>#define N 5using 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 graphvoid 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(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