Floyd Warshall Algorithm

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a graph-analysis algorithm that calculates shortest paths between all pairs of nodes in a graph. It is a dynamic programming algorithm with O(|V|³) time complexity and O(|V|²) space complexity. For path reconstruction, see here; for a more efficient algorithm for sparse graphs, see Johnson's algorithm.

 

Contents

Original source taken from Floyd-Warshall algorithm.

Conveniently, when calculating the $k$th case, one can overwrite the information saved from the computation of $k-1$. This means the algorithm uses quadratic memory. Be careful to note the initialization conditions:

 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
 2    (infinity if there is none).
 3    Also assume that n is the number of vertices and edgeCost(i,i)=0
 4 */
 5
 6 int path[][];
 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
 8    from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
 9    edgeCost(i,j) or infinity if there is no edge between i and j.
10 */
11
12 procedure FloydWarshall ()
13    for ${\mathit {k}}:=1$ to ${\mathit {n}}$
14       for each ${\mathit {(i,j)}}$ in $\lbrace 1,..,n\rbrace ^{2}$
15          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

   

Further reading and resources