[EM] Floyd-Warshall algorithm

[Andrew Myers]

Hi all,

The "Floyd algorithm" is usually called the Floyd-Warshall all-pairs shortest
path algorithm. This algorithm computes the cost of the "best path" in a
weighted, directed graph. The notion of 'best' and 'cost' are defined by two
operations we can call 'min' and '+', respectively. As long as the actual
mathematical operations have the right algebraic properties, the algorithm will
work. The core of the algorithm updates the matrix as follows:

    m[i][j] = 'min'(m[i][j], m[i][k] '+' m[k][j])

For example, if we choose 'min' = min and '+' = +, then the cost of a path
is the sum of the weights of the edges and the algorithm finds the lowest-cost
path.

If we choose 'min' = max and '+' = min, then the cost of a path is
the lowest-weight edge and the algorithm finds the highest-weight path.
This is the particular choice of operators that results in selecting
the beatpath winner.

Many other choices for 'min' and '+' are possible, of course.

When implemented correctly it has O(V^3) running time where V is the number of
vertices (nodes) in the graph.

-- Andrew Myers