[EM] Typo in "Proof that Floyd finishes in 1 pass?"

Rob Speer rspeer at MIT.EDU
Mon Dec 22 11:36:02 PST 2003

On Mon, Dec 22, 2003 at 09:28:37AM +0000, MIKE OSSIPOFF wrote:
> I'm asking if anyone can prove that the BeatpathWinner algorithm that I 
> posted a few days ago would find the strongest beatpath between each 
> ordered pair of candidates _in one pass_ if the order of the indices were 
> re-arranged.

You accept that the Floyd-Warshall algorithm is proven, right? I don't
have my copy of CLR around.

Floyd-Warshall shortest paths is a special case of the Floyd-Warshall
algorithm, where the path weight is calculated with + and the minimum
is taken. Floyd-Warshall can also be used for the transitive closure, or
for beatpaths, because the algorithm doesn't depend on the particular
operations that are used.

Rob Speer

More information about the Election-Methods mailing list