Floyd-Warshall Shortest Path Algorithm
Below are some of the key points of Floyd-Warshall’s shortest path for all node pairs
- Floyd-Warshall algorithm finds the shortest path between all pairs of vertices (in terms of distance / cost ) in a directed weighted graph containing positive and negative edge weights.
- This algorithm works on graphs without any negative weight cycles.
- This algorithm uses a recursive function Shortest_Path ( i, j, k ), where i is the source, j is the destination and [ 1…k ] are the intermediate nodes that can be used for going from i to j. Thus, Shortest_Path ( i, j, k ) = Minimum ( Shortest_Path ( i, j, k-1 ) , Shortest_Path ( i, k, k-1 ) + Shortest_Path ( k, j, k-1 ) ) Where, The shortest path does not visit an intermediate node k Shortest_Path ( i, j, k-1 ) : The shortest path from i to j does not take an intermediate node k but there are still ( k-1 ) nodes to choose from. The shortest path visits an intermediate node k Shortest_Path ( i, k, k-1 ) : The shortest path from i to k with intermediate nodes ( k-1 ) to choose from. Shortest_Path ( k, j, k-1 ) : The shortest path from k to j with intermediate nodes ( k-1 ) to choose from. Using this recursive function as a base, the Floyd-Warshall finds the shortest path from node i to node j using all the available intermediate nodes [ 1 … k ].
Algorithm : Floyd-Warshall 1. Create a two-dimensional array of size n x n for storing the length of the shortest path from every node to every other node. n is the number of nodes in the graph. Initialize all the cells of this array to ∞. 2. For every node i in the graph, initialize the distance of the node to itself as 0. Distance [ i ] [ i ] = 0. 3. For every edge (u, v) in the graph, initialize the distance array as the weight of the edge. Distance [ u ] [ v ] = Weight of (u, v) 4. For every node k in [ 1..n ] do For every node i in [ 1..n ] do For every node j in [ 1..n ] do If ( Distance [ i ] [ j ] > Distance [ i ] [ k ] + Distance [ k ] [ j ] ) : Distance [ i ] [ j ] = Distance [ i ] [ k ] + Distance [ k ] [ j ]
Floyd-Warshall path construction example
Consider the shortest path in terms of weight / distance between node Source ( 1 ) - Destination ( 3 ) : [ 1 2 3 ] Case 1 : The shortest path from a node to itself is the node itself. i.e next [ i ] [ i ] = i. Example : next [ 1 ] [ 1 ] = 1 i.e Next node from 1 to reach 1 is 1. Example : next [ 3 ] [ 3 ] = 3 i.e Next node from 3 to reach 3 is 3. Case 2 : If the shortest path from node i to node j does not visit any intermediate node, next [ i ] [ j ] = j. Example : next [ 1 ] [ 2 ] = 2 i.e Next node from 1 to reach 2 is 2. Example : next [ 2 ] [ 3 ] = 3 i.e Next node from 2 to reach 3 is 3. Case 3 : If the shortest path from node i to node j visits an intermediate node k, next [ i ] [ j ] = next [ i ] [ k ] Example : next [ 1 ] [ 3 ] = next [ 1 ] [ 2 ] = 2 i.e Next node from 1 to 3 is 2.
To construct the path from Source 1 - Destination 3 the algorithm follows the below steps
- Insert source node 1 in the path [ 1 ]
- Find the next node in the path from 1 - 3 i.e next [ 1 ] [ 3 ] = 2. Insert node 2 in the path [ 1 2 ]. 2 becomes the source node.
- Find the next node in the path from 2 - 3 i.e next [ 2 ] [ 3 ] = 3. Insert node 3 in the path [ 1 2 3 ]. 3 becomes the source which is now same as the destination.
Algorithm : Path construction ( Source src, Destination dst ) 1. If next [ src ] [ dst ] == -1 then no path exist. return empty path [ ]. 2. Insert path = [ src ] 3. While ( src != dst ) 4. source = next [ src ] [ dst ] 5. Append src to path
Graph type : Designed for directed weighted graphs containing positive and negative edge weights and no negative weight cycles.
Data structure used for storing graph : Edge list for storing the edges and their corresponding weights.
Time complexity : O ( N 3 ). N is the number of vertices / node in the graph.
Floyd-Warshall’s all pairs shortest path implementation.
# Example : Graph
# 1
# /|\
# / | \
# 9/ |7 \3
# / 3 | \
# 0----4----2
# \ | 1 /
# 2\ |1 /-2
# \ | /
# \|/
# 3
#
class Edge :
def __init__(self, src, dst, weight) :
self.src = src
self.dst = dst
self.weight = weight
class Graph:
def __init__(self, arg_nodes):
self.nodes = arg_nodes
# Edge weight is a dictionary for storing the weight of the edges { "src-dst" : weight }
self.edge_list = []
# distance is a 2-dimensional array that stores the shortest distance between [src][dst]
self.distance = [999999999] * arg_nodes
# next is a 2-dimensional array that stores the node next to the source. This is used
# for path construction between [src][dst]
self.next = [-1] * arg_nodes
for i in range(arg_nodes):
self.distance[i] = [999999999] * arg_nodes
self.next[i] = [-1] * arg_nodes
def AddEdge (self, src, dst, weight, isbidirectional = True):
e = Edge(src, dst, weight)
self.edge_list.append(e)
if (isbidirectional):
e = Edge(dst, src, weight)
self.edge_list.append(e)
def Floyd_Warshall(self):
for i in range (self.nodes):
self.distance[i][i] = 0
self.next[i][i] = i
for edge in self.edge_list:
weight = edge.weight
u = edge.src
v = edge.dst
self.distance[u][v] = weight
self.next[u][v] = v
for k in range(self.nodes):
for i in range(self.nodes):
for j in range(self.nodes):
if (self.distance[i][j] > self.distance[i][k] + self.distance[k][j]):
self.distance[i][j] = self.distance[i][k] + self.distance[k][j]
self.next[i][j] = self.next[i][k]
print("Shortest distance between nodes\n")
for u in range(self.nodes):
for v in range(u+1, self.nodes):
print("Distance ( " + str(u) + " - " + str(v) + " ) : " + str(self.distance[u][v]))
self.PathConstruction(u, v)
# Construct path from source node to destination node
def PathConstruction (self, src, dst):
print("# Path between " + str(src) + " and " + str(dst) + " : ", end = ' ')
if (self.next[src][dst] == -1):
print("No path exists")
else:
path = []
path.append(src)
while (src != dst):
src = self.next[src][dst]
path.append(src)
for node in path:
print(str(node) + " ", end = ' ')
print("\n")
def main():
g = Graph(5)
# Edges from node 0
g.AddEdge(0, 1, 9)
g.AddEdge(0, 3, 2)
g.AddEdge(0, 4, 3)
# Edges from node 1
g.AddEdge(1, 2, 3)
g.AddEdge(1, 4, 7)
# Edges from node 2
# Edge from 2 -> 3 is unidirectional. If it was bidirectional, it would introduce negative weight cycle
# causing the Floyd-Warshall algorithm to fail.
g.AddEdge(2, 3, -2, False)
g.AddEdge(2, 4, 1)
# Edges from node 3
g.AddEdge(3, 4, 1)
g.Floyd_Warshall()
if __name__ == "__main__":
main()
Output
Shortest distance between nodes
Distance ( 0 - 1 ) : 7
# Path between 0 and 1 : 0 4 2 1
Distance ( 0 - 2 ) : 4
# Path between 0 and 2 : 0 4 2
Distance ( 0 - 3 ) : 2
# Path between 0 and 3 : 0 3
Distance ( 0 - 4 ) : 3
# Path between 0 and 4 : 0 4
Distance ( 1 - 2 ) : 3
# Path between 1 and 2 : 1 2
Distance ( 1 - 3 ) : 1
# Path between 1 and 3 : 1 2 3
Distance ( 1 - 4 ) : 2
# Path between 1 and 4 : 1 2 3 4
Distance ( 2 - 3 ) : -2
# Path between 2 and 3 : 2 3
Distance ( 2 - 4 ) : -1
# Path between 2 and 4 : 2 3 4
Distance ( 3 - 4 ) : 1
# Path between 3 and 4 : 3 4
#include<iostream>
#include<list>
#include<vector>
using namespace std;
/*
1
/|\
/ | \
9/ |7 \3
/ 3 | \
0----4----2
\ | 1 /
2\ |1 /-2
\ | /
\|/
3
*/
class Edge {
public:
int src;
int dst;
int weight;
Edge () {}
Edge (int src, int dst, int weight) {
this->src = src;
this->dst = dst;
this->weight = weight;
}
};
class Graph {
private:
list<Edge> edge_list;
int nodes;
// distance is a 2-dimensional array that stores the shortest distance between [src][dst]
vector<vector<int>> distance;
// next is a 2-dimensional array that stores the node next to the source. This is used
// for path construction between [src][dst]
vector<vector<int>> next;
public:
Graph() {}
Graph (int n) {
nodes = n;
distance.resize(n);
next.resize(n);
for (int i=0; i<n; i++) {
distance[i].resize(n, 999999999); // 999999999 indicates infinite distance
next[i].resize(n, -1);
}
}
void AddEdge (int src, int dst, int weight, bool isbidirectional) {
Edge e(src, dst, weight);
edge_list.push_back(e);
if (isbidirectional) {
Edge e(dst, src, weight);
edge_list.push_back(e);
}
}
void Floyd_Warshall() {
for (int i=0; i<nodes; i++) {
distance[i][i] = 0;
next[i][i] = i;
}
for (auto edge : edge_list) {
int u = edge.src;
int v = edge.dst;
distance[u][v] = edge.weight;
next[u][v] = v;
}
for (int k=0; k<nodes; k++) {
for (int i=0; i<nodes; i++) {
for (int j=0; j<nodes; j++) {
if (distance[i][j] > distance[i][k] + distance[k][j]) {
distance[i][j] = distance[i][k] + distance[k][j];
next[i][j] = next[i][k];
}
}
}
}
cout << "Shortest distance between nodes" << endl;
for (int u=0; u<nodes; u++) {
for (int v=u+1; v<nodes; v++) {
cout << "\nDistance ( " << u << " - " << v << " ) : " << distance[u][v] << endl;
PathConstruction(u, v);
}
}
}
// Construct path from source node to destination node
void PathConstruction (int src, int dst) {
cout << "# Path between " << src << " and " << dst << " : ";
if (next[src][dst] == -1) {
cout << "No path exists" << endl;
} else {
vector<int> path;
path.push_back(src);
while (src != dst) {
src = next[src][dst];
path.push_back(src);
}
for (auto& it : path)
cout << it << " ";
cout << endl;
}
}
};
int main() {
Graph g(5);
// Edges from node 0
// AddEdge(src, dst, weight, bi-directional(true/false))
g.AddEdge(0, 1, 9, true);
g.AddEdge(0, 3, 2, true);
g.AddEdge(0, 4, 3, true);
// Edges from node 1
g.AddEdge(1, 2, 3, true);
g.AddEdge(1, 4, 7, true);
// Edges from node 2
// Edge from 2 -> 3 is unidirectional. If it was bidirectional, it would introduce negative weight cycle
// causing the Floyd-Warshall algorithm to fail.
g.AddEdge(2, 3, -2, false);
g.AddEdge(2, 4, 1, true);
// Edges from node 3
g.AddEdge(3, 4, 1, true);
g.Floyd_Warshall();
return 0;
}
Output
Shortest distance between nodes
Distance ( 0 - 1 ) : 7
# Path between 0 and 1 : 0 4 2 1
Distance ( 0 - 2 ) : 4
# Path between 0 and 2 : 0 4 2
Distance ( 0 - 3 ) : 2
# Path between 0 and 3 : 0 3
Distance ( 0 - 4 ) : 3
# Path between 0 and 4 : 0 4
Distance ( 1 - 2 ) : 3
# Path between 1 and 2 : 1 2
Distance ( 1 - 3 ) : 1
# Path between 1 and 3 : 1 2 3
Distance ( 1 - 4 ) : 2
# Path between 1 and 4 : 1 2 3 4
Distance ( 2 - 3 ) : -2
# Path between 2 and 3 : 2 3
Distance ( 2 - 4 ) : -1
# Path between 2 and 4 : 2 3 4
Distance ( 3 - 4 ) : 1
# Path between 3 and 4 : 3 4
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
/*
1
/|\
/ | \
9/ |7 \3
/ 3 | \
0----4----2
\ | 1 /
2\ |1 /-2
\ | /
\|/
3
*/
class Edge {
int src;
int dst;
int weight;
Edge(int src, int dst, int weight) {
this.src = src;
this.dst = dst;
this.weight = weight;
}
}
class Graph {
int nodes;
// distance is a 2-dimensional array that stores the
// shortest distance between [src][dst]
int distance[][];
// next is a 2-dimensional array that stores the node next to src.
// This is used for the path construction between [src][dst]
int next[][];
List<Edge> edge_list = new ArrayList<Edge>();
Graph (int n) {
nodes = n;
distance = new int[n][n];
next = new int[n][n];
for (int i=0; i<n; i++) {
Arrays.fill(distance[i], 999999999); // 999999999 indicates infinite distance
Arrays.fill(next[i], -1);
}
}
void AddEdge (int src, int dst, int weight, boolean isbidirectional) {
Edge e = new Edge(src, dst, weight);
edge_list.add(e);
if (isbidirectional) {
e = new Edge(dst, src, weight);
edge_list.add(e);
}
}
void Floyd_Warshall() {
for (int i=0; i<nodes; i++) {
distance[i][i] = 0;
next[i][i] = i;
}
for (Edge it : edge_list) {
int weight = it.weight;
int u = it.src;
int v = it.dst;
distance[u][v] = weight;
next[u][v] = v;
}
for (int k=0; k<nodes; k++) {
for (int i=0; i<nodes; i++) {
for (int j=0; j<nodes; j++) {
if (distance[i][j] > distance[i][k] + distance[k][j]) {
distance[i][j] = distance[i][k] + distance[k][j];
next[i][j] = next[i][k];
}
}
}
}
System.out.println( "Shortest distance between nodes");
for (int u=0; u<nodes; u++) {
for (int v=u+1; v<nodes; v++) {
System.out.println("\nDistance ( " + u + " - " + v + " ) : " + distance[u][v]);
PathConstruction(u, v);
}
}
}
// Construct path from source node to destination node
void PathConstruction (int src, int dst) {
System.out.print("# Path between " + src + " and " + dst + " : ");
if (next[src][dst] == -1) {
System.out.println( "No path exists");
} else {
List<Integer> path = new ArrayList<Integer>();
path.add(src);
while (src != dst) {
src = next[src][dst];
path.add(src);
}
for (int n : path)
System.out.print(n + " ");
System.out.println();
}
}
public static void main(String[] args) {
Graph g = new Graph(5);
// Edges from node 0
g.AddEdge(0, 1, 9, true);
g.AddEdge(0, 3, 2, true);
g.AddEdge(0, 4, 3, true);
// Edges from node 1
g.AddEdge(1, 2, 3, true);
g.AddEdge(1, 4, 7, true);
// Edges from node 2
// Edge from 2 -> 3 is unidirectional. If it was bidirectional, it would introduce negative weight cycle
// causing the Floyd-Warshall algorithm to fail.
g.AddEdge(2, 3, -2, false);
g.AddEdge(2, 4, 1, true);
// Edges from node 3
g.AddEdge(3, 4, 1, true);
g.Floyd_Warshall();
}
}
Output
Shortest distance between nodes
Distance ( 0 - 1 ) : 7
# Path between 0 and 1 : 0 4 2 1
Distance ( 0 - 2 ) : 4
# Path between 0 and 2 : 0 4 2
Distance ( 0 - 3 ) : 2
# Path between 0 and 3 : 0 3
Distance ( 0 - 4 ) : 3
# Path between 0 and 4 : 0 4
Distance ( 1 - 2 ) : 3
# Path between 1 and 2 : 1 2
Distance ( 1 - 3 ) : 1
# Path between 1 and 3 : 1 2 3
Distance ( 1 - 4 ) : 2
# Path between 1 and 4 : 1 2 3 4
Distance ( 2 - 3 ) : -2
# Path between 2 and 3 : 2 3
Distance ( 2 - 4 ) : -1
# Path between 2 and 4 : 2 3 4
Distance ( 3 - 4 ) : 1
# Path between 3 and 4 : 3 4