[EM] Correctness of Floyd-Warshall for beatpaths

[Andrew Myers]

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.

-- Andrew