The gist of Floyd-Warshall all pairs shortest path algorithm

- 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. - Floyd-Warshall algorithm works on graphs without any negative weight cycles.
- Floyd-Warshall algorithm is based on 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

1. Insert source node **1** in the path **[ 1 ]**

2. 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.

3. 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 : Floyd-Warshall 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 of Flyod-Warshall’s algorithm : O (N^3)**. **N** is the number of vertices / node in the graph.

**C++ : Implementation of Floyd-Warshall’s all pairs shortest path algorithm in C++11**

```
#include<iostream>
#include<map>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
/*
1
/|\
/ | \
9/ |7 \3
/ 3 | \
0----4----2
\ | 1 /
2\ |1 /-2
\ | /
\|/
3
*/
class Graph {
private:
map<PII, int> edge_weight;
int nodes;
vector<vector<int>> distance; // stores the shortest distance between [src][dst]
vector<vector<int>> next; // stores the node next to src for a path between [src][dst]
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 AddEdgeWeight (int src, int dst, int weight, bool isbidirectional = true) {
edge_weight.insert(pair<PII,int>(make_pair(src, dst), weight));
if (isbidirectional)
edge_weight.insert(pair<PII,int>(make_pair(dst, src), weight));
}
void Floyd_Warshall() {
for (int i=0; i<nodes; i++) {
distance[i][i] = 0;
next[i][i] = i;
}
for (auto& it: edge_weight) {
PII edge = it.first;
int weight = it.second;
int u = edge.first;
int v = edge.second;
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];
}
}
}
}
cout << "Shortest distance between nodes" << endl;
for (int u=0; u<nodes; u++) {
for (int v=u+1; v<nodes; v++) {
cout << "Distance ( " << u << " - " << v << " ) : " << distance[u][v];
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
g.AddEdgeWeight(0, 1, 9);
g.AddEdgeWeight(0, 3, 2);
g.AddEdgeWeight(0, 4, 3);
// Edges from node 1
g.AddEdgeWeight(1, 2, 3);
g.AddEdgeWeight(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.AddEdgeWeight(2, 3, -2, false);
g.AddEdgeWeight(2, 4, 1);
// Edges from node 3
g.AddEdgeWeight(3, 4, 1);
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
```

All rights reserved.