Essays/Floyd

The Floyd algorithm (aka. Floyd–Warshall algorithm) computes the shortest paths between each pair of vertices in a digraph with weighted edges.

The input of the algorithm is a dense digraph with real (not necessarily positive) edge weights. We represent this as a matrix whose rows and columns correspond to the nodes of the graph (in the same order) and whose elements are the weights of the edges (or infinity where there's no edge).

I will be using the example input below, but of course I'm asking for a general method.

   ]wtm=: _6]\0 2 5 _ _ _ _ 0 4 1 3 _ _ _ 0 _ _2 _ _ _ 4 0 _ 5 _ _ _ _1 0 6 _ _ _ _ _ 0
0 2 5  _  _ _
_ 0 4  1  3 _
_ _ 0  _ _2 _
_ _ 4  0  _ 5
_ _ _ _1  0 6
_ _ _  _  _ 0

Here's a drawing of this graph (nodes are listed in order ABCDEF in the matrix).

The output shall be a matrix of the lengths of shortest paths between each two nodes.

The simplest way to generate this is the following imperative algorithm. We take the table A where A(x,y) starts as the weight of the edge from x to y, that is, A is the input matrix. We change the value of A such that in each intermediate step, A(x,y) is the length of some path from x to y, that is, an upper bound for the length of the shortest path between these two nodes. The iteration step goes by replacing each A(x,y) with the minimum of A(x,z)+A(z,y) for z in the set of nodes. (It doesn't matter whether we compute the new values and replace the whole matrix at once, or write the values to A immediately.) After a few iterations, the matrix will stabilize to the output. This takes O(n^3 log n) runtime for a graph with n nodes.

A J implementation of this is very concise.

   rpow=: <./ .+~^:_
   ]dist2=: rpow wtm
0 2 5  2  3 7
_ 0 4  1  2 6
_ _ 0 _3 _2 2
_ _ 4  0  2 5
_ _ 3 _1  0 4
_ _ _  _  _ 0

The Floyd algorithm is a tricky modification of the above scheme, which runs in O(n^3) time. We initialize A to the matrix of edge weights as above. Then we make a loop on z running over each node, and for each one, we replace A(x,y) with the minimum of A(x,z)+A(z,y) and A(x,y). After just one such loop with z, we get the final result. (Again, it doesn't matter if we replace the elements of A immediately or replace the whole matrix at once for each z value.)

The J code for this is the following.

   floyd=: 3 :('for_j. i.#y';'do. y=. y <. j ({"1 +/ {) y';'end.';'y')
   dist2-: dist=: floyd wtm
1