[EM] Floyd algorithm?

[Markus Schulze]

Dear Mike,

you wrote (17 Dec 2003):
> Wrong. I don't call that the Floyd algorithm.

I wrote (17 Dec 2003):
> You do. You call that the Floyd algorithm
> (http://electionmethods.org/CondorcetSSD.py):
>
> > Determine "beatpath" magnitudes array using the Floyd Algorithm:
> > Def[i,j] will be the maximum beatpath magnitudes array. The i,j
> > entry is the greatest magnitude of any beatpath from i to j. A
> > beatpath's magnitude is the magnitude of its weakest defeat.

You wrote (17 Dec 2003):
> Wrong again. You aren't being entirely clear with us about exactly
> what you mean by"that". Perhaps you're confused about what you mean.
>
> You posted a little fragment of a Python program. And, in that fragment,
> some of the lines weren't even complete. You said I called that the Floyd
> algorithm. I replied that I have never called that line-truncated fragment
> anything. Did i call the Python program from which you got that fragment
> the Floyd algorithm? That's another matter. I didnt call your poorly-copied
> fragment anything, including the Floyd algorithm.

In so far as I gave a concrete quotation where you call your implementation
"Floyd algorithm", how can you still claim that I misquoted you?

*********

You wrote (17 Dec 2003):
> I couldn't care less if it's the Floyd algorithm. If it isn't, then I'll
> tell Russ to delete that name from the website. When we put it at the
> website, I at that time believed that it was the Floyd algorithm because it
> was the corrected versioin of something that you had posted to EM, calling
> it the Floyd algorithm.
>
> What you'd posted differed by only making one pass throiugh the 3-candiate
> permutations. But one pass isn't guaranteed to find all the strongest
> beatpaths.
>
> Now it occurs to me that maybe your Floyd algorithm isn't intended to
> do that. After all, you do call it the shortest-path algorithm, not the
> strongest path algorithm. I assumed at the time that your algorithm was
> supposed to find the strongest beatpaths, and that yoiu'd accidentally left
> out the code to repeat the passes till the task is complete. So I corrected
> what you'd posted so that it would do that, and called it the Floyd
> algorithm.

What you call "the corrected versioin" is actually a falsified version.
When you use the correct order of the indices in the triple-loop, then
one pass through the 3-candidate permutations _does_ guarantee to find
all the strongest paths. Floyd proved this in 1962. This is the reason
why it is called the "Floyd algorithm".

You wrote (17 Dec 2003):
> I re-emphasize that I didn't get our strongest beatpaths algorithm
> from you or Floyd, or anyone but Steve Eppley, who suggested it.

It is sad that you didn't get your strongest path algorithm from me
or Floyd; if you did it, it had a runtime of O(N^3) and not of O(N^5).

Markus Schulze