[EM] Floyd Algorithm?
Markus Schulze
markus.schulze at alumni.tu-berlin.de
Thu Dec 18 02:45:02 PST 2003
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
More information about the Election-Methods
mailing list