[EM] Floyd Algorithm?

[Markus Schulze]

Dear Mike,

you wrote (17 Dec 2003):

> Wrong. I don't call that the Floyd algorithm.

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.

But the then used algorithm is clearly not the Floyd algorithm
(http://electionmethods.org/CondorcetSSD.py):

>    changing = 1
>
>    while changing:
>
>        changing = 0
>
>        for i in range(nc):
>            for j in range(nc):
>                for k in range(nc):
>
>                    dmin = min ( Def[i,j], Def[j,k] )
>
>                    if Def[i,k] < dmin:
>                        Def[i,k] = dmin
>                        changing = 1

The Floyd algorithm has a runtime O(N^3), where N is the number of
candidates. But what you call the "Floyd Algorithm" has a runtime
O(N^5).

******

You wrote (17 Dec 2003):
> It's part of the algorithm that I send people for counting
> BeatpathWinner. I'll post that BeatpathWinner algorithm here
> in a few minutes.

A correct version of the Floyd algorithm can be found in my paper
"A New Monotonic and Clone-Independent Single-Winner Election Method":
http://groups.yahoo.com/group/election-methods-list/files/nmciswem.pdf

Markus Schulze