[EM] Floyd-Warshall algorithm
Andrew Myers
andru at cs.cornell.edu
Fri Dec 19 08:03:04 PST 2003
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
More information about the Election-Methods
mailing list