[EM] BeatpathWinner Algorithm

MIKE OSSIPOFF nkklrp at hotmail.com
Thu Dec 18 03:23:01 PST 2003

Here is an algorithm to implement BeatpathWinner. It seems to me that 
someone called the strongest beatpaths algorithm the Floyd algorithm. But 
maybe not. When Markus said that the fragment of code that he quoted didn't 
work to find the shortest path, he may have been referring to the overall 
algorithm or program from which his fragment was taken. That may well be, 
because the strongest beatpaths algorithm used here isn't intended to find 
shortest paths. It's intended to find strongest beatpaths.

BeatpathWinner Algorithm:

The algorithm below isn't written here in any
particular programming language. But it would only
require a few small  changes to make it into any
programming language.

Here's the BeatpathWinner algorithm:

First we make the strongest beatpaths array.

Place the defeat-strengths into the strongest
beatpaths array, B(i,j):

If i  beats j, then B(i,j) = the number of people who
have ranked i over j.

If i doesn't beat j, then B(i,j) = 0.

repeat = 1
while repeat = 1:
  change = 0
  for i = 1 to N
     for j =  1 to N
        for k = 1 to N
           least = min(B(i,j), B(j,k))
           if least > B(i,k):
              B(i,k) = least
              change =1
if change= 0
    repeat = 0

When this has been done, you have the strongest
beatpaths array, B(i,j), where B(i,j) is the strength
of the strongest beatpath from i to j. (If there's no
beatpath from i to j, then B(i,j) = 0).

Then B(i,j) is used to find the winners of

for i = 1 to N
win(i) = 1

for i = 1 to N
  for j = 1 to N
     if B(j,i) > B(i,j)
        win(i) = 0

print "The winners are:"
for i = 1 to N
if win(i) = 1
    print i

[end of BeatpathWinner algorithm]

Grab our best dial-up Internet access offer: 6 months @$9.95/month.  

More information about the Election-Methods mailing list