Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is an efficient DynamicProgramming algorithm that computes the shortest path between all pairs of vertices in a directed (or undirected) graph. This is arguably the easiest-to-implement algorithm around for computing shortest paths on programming contests.
// Basic Floyd Warshall Implementation
// input:
// d is a distance matrix for n nodes.
// e.g. d[i][j] is the distance to move directly from i to j.
// if no direct link from i to j then initialize d[i][j] = Infinity.
// the distance from a node to itself is 0. Initialize d[i][i] = 0 for all i.
// p is a predecessor matrix. it enables you to reconstruct the shortest paths.
// p[i][j] should be initialized to i.
// output:
// d[i][j] contains the total cost along the shortest path from i to j.
// p[i][j] contains the predecessor of j on the shortest path from i to j.
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k]+d[k][j];
p[i][j] = p[k][j];
}
// Recursive function to reconstruct the shortest path from i to j
// using the predecessor matrix computed above
print_path (int i, int j) {
if (i!=j)
print_path(i,p[i][j]);
print(j);
}
// input:
// d is a distance matrix for n nodes.
// e.g. d[i][j] is the distance to move directly from i to j.
// if no direct link from i to j then initialize d[i][j] = Infinity.
// the distance from a node to itself is 0. Initialize d[i][i] = 0 for all i.
// p is a predecessor matrix. it enables you to reconstruct the shortest paths.
// p[i][j] should be initialized to i.
// output:
// d[i][j] contains the total cost along the shortest path from i to j.
// p[i][j] contains the predecessor of j on the shortest path from i to j.
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k]+d[k][j];
p[i][j] = p[k][j];
}
// Recursive function to reconstruct the shortest path from i to j
// using the predecessor matrix computed above
print_path (int i, int j) {
if (i!=j)
print_path(i,p[i][j]);
print(j);
}
Applications
- All-pairs shortest path - Computing shortest paths between every pair of vertices in a directed graph.
- Transitive closure. Basically for determining reachability of nodes. Transitive closure has many uses in determining relationships between things.
// Transitive closure variant of Floyd-Warshall
// input: d is an adjacency matrix for n nodes.
// reachability of a node to itself e.g. d[i][i] should be initialized to 1.
// output: d[i][j]=1 will mean j can be reached from i.
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]=='1' && d[k][j]=='1') d[i][j]='1';
// input: d is an adjacency matrix for n nodes.
// reachability of a node to itself e.g. d[i][i] should be initialized to 1.
// output: d[i][j]=1 will mean j can be reached from i.
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]=='1' && d[k][j]=='1') d[i][j]='1';
- Detecting negative-weight cycles in graphs. (If there is a negative weight cycle, the distance from a the start node to itself will be negative after running the algorithm)
- Bipartiteness - (Although you can also do bipartiteness checking based on single-source shortest paths algorithms like Dijkstra). Basically, you can detect whether a graph is bipartite via parity. Set all edges to a weight of 1, all vertices at an odd shortest-distance away from some arbitrary root V are in one subset, all vertices at an even distance away are in another subset.
- Minimax - Minimax in graph problems involves finding a path between two nodes that minimizes the maximum cost along the path. (Example problems include finding feasible paths to take by car with a limited fuel tank and rest stations at every node). See below for the tweak for Floyd-Warshall that enables finding minimax. You can also add in an update to a predecessor matrix in order to keep track of the actual path found.
// Minimax variant of Floyd-Warshall example
// input: d is an distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the minimax path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
// input: d is an distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the minimax path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
- Maximin - the other way around from Minimax - here you have problems where you need to find the path the maximizes the minimum cost along a path. (Example problems include trying to maximize the load a cargo truck can take when roads along a path may have a weight limit, or trying to find a network routing path that meets a minimum bandwidth requirement for some application). See below for the tweak for Floyd-Warshall that enables finding maximin.
// Maximin variant of Floyd-Warshall example
// input: d is an distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the maximin path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
// input: d is an distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the maximin path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
- Safest path - Similar in construction of Floyd-Warshall to minimax and maximin - Need to maximize the product of probabilities of survival along a path. Simply change the max to a min to find the most dangerous path.
// Safest path variant of Floyd-Warshall example
// input: p is an probability matrix (probability of survival) for n nodes
// e.g. p[i][j] is the probability of survival moving directly from i to j.
// the probability from a node to itself e.g. p[i][i] should be initialized to 1
// output: p[i][j] will contain the probability of survival using the safest path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
p[i][j] = max(p[i][j], p[i][k] * p[k][j]);
// input: p is an probability matrix (probability of survival) for n nodes
// e.g. p[i][j] is the probability of survival moving directly from i to j.
// the probability from a node to itself e.g. p[i][i] should be initialized to 1
// output: p[i][j] will contain the probability of survival using the safest path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
p[i][j] = max(p[i][j], p[i][k] * p[k][j]);