Floyd-Warshall algorithm is a procedure, which is used to find the shorthest (longest) paths among all pairs of nodes in a graph, which does not contain any cycles of negative lenght. The main advantage of Floyd-Warshall algorithm is its simplicity.
Description
Floyd-Warshall algorithm uses a matrix of lengths as its input. If there is an edge between nodes
and
, than the matrix
contains its length at the corresponding coordinates. The diagonal of the matrix contains only zeros. If there is no edge between edges
and
, than the position
contains positive infinity. In other words, the matrix represents lengths of all paths between nodes that does not contain any intermediate node.
In each iteration of Floyd-Warshall algorithm is this matrix recalculated, so it contains lengths of paths among all pairs of nodes using gradually enlarging set of intermediate nodes. The matrix , which is created by the first iteration of the procedure, contains paths among all nodes using exactly one (predefined) intermediate node.
contains lengths using two predefined intermediate nodes. Finally the matrix
uses
intermediate nodes.
This transformation can be described using the following recurrent formula:
Because this transformation never rewrites elements, which are to be used to calculate the new matrix, we can use the same matrix for both and
.
Code
procedure [array] FloydWarshall(D, P)
for k in 1 to n do
for i in 1 to n do
for j in 1 to n do
if D[i][j] > D[i][k] + D[k][j] then
D[i][j] = D[i][k] + D[k][j]
P[i][j] = P[k][j]
return P
/**
* Floyd-Warshall algorithm. Finds all shortest paths among all pairs of nodes
* @param d matrix of distances (Integer.MAX_VALUE represents positive infinity)
* @return matrix of predecessors
*/
public static int[][] floydWarshall(int[][] d) {
int[][] p = constructInitialMatixOfPredecessors(d);
for (int k = 0; k < d.length; k++) {
for (int i = 0; i < d.length; i++) {
for (int j = 0; j < d.length; j++) {
if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) {
continue;
}
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
p[i][j] = p[k][j];
}
}
}
}
return p;
}
/**
* Constructs matrix P0
* @param d matrix of lengths
* @return P0
*/
private static int[][] constructInitialMatixOfPredecessors(int[][] d) {
int[][] p = new int[d.length][d.length];
for (int i = 0; i < d.length; i++) {
for (int j = 0; j < d.length; j++) {
if (d[i][j] != 0 && d[i][j] != Integer.MAX_VALUE) {
p[i][j] = i;
} else {
p[i][j] = -1;
}
}
}
return p;
}
Asymptotic complexity
The algorithm consists of three loops over all nodes, and the most inner loop contains only operations of a constant complexity. Hence the asymptotic complexity of the whole Floyd-Warshall algorithm is , where
is number of nodes of the graph.
Example
Matrix of predecessors
In order to return shortest (longest) paths among all pairs of nodes, we construct during transformations of matrix also output matrix
(matrix of predecessors). The matrix can be read as follows: if we want to reconstruct the (shortest) path between nodes
and
, than we look at the element at corresponding coordinates. If its value is
, than there is no path between these nodes, otherwise the value of the element denotes predecessor of
on the path from
to
. So we repeat this procedure, while the preceding node is not equal to
.
Code
function getPath(P, i, j)
if i == j then
write(i)
else if P[i][j] = 0 then
write("Path does not exist")
else
getPath(P, i, P[i][j])
write(j)
Example
Detection of cycles of (non)negative length
Floyd-Warshall algorithm can be easily modified to detect cycles. If we fill negative infinity value at the diagonal of the matrix and run the algorithm, than the matrix of predecessors will contain also all cycles in the graph (the diagonal will not contain only zeros, if there is a cycle in the graph).
Sources
- KOLÁŘ, Josef. Teoretická informatika. 2. ed. Praha : Česká informatická společnost, 2004. 205 p. ISBN 80-900853-8-5.
- HANZÁLEK, Zdeněk. Kombinatorická optimalice, Nejkratší cesty - slides k přednáškám.