[EM] Correctness of Floyd-Warshall for beatpaths
andru at cs.cornell.edu
Tue Dec 23 08:57:08 PST 2003
Because there has been continuing concern about the algorithm, I looked
up more information in the standard textbook I referred to in an earlier
email (Cormen, Leiserson, and Rivest).
The Floyd-Warshall algorithm (so named because the algorithm was
proposed by Floyd but based on a theorem by Warshall) works on any
closed semiring. A semiring is defined by two operations (which I called
min and + in my earlier mail). For computing beatpaths, the operations
are max and min respectively. Showing that max and min define a
semiring, and that the required closure properties hold, is
straightforward. I refer those who are interested to the text above.
More information about the Election-Methods