﻿ Floyd-Warshall algorithm  Graph and matrix of lengths

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.