[EM] BeatpathWinner Algorithm

[MIKE OSSIPOFF]

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
           endif
       endfor
    endfor
endfor
if change= 0
    repeat = 0
endif
endwhile

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
BeatpathWinner:

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

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

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

[end of BeatpathWinner algorithm]
_____

_________________________________________________________________
Grab our best dial-up Internet access offer: 6 months @$9.95/month.  
http://join.msn.com/?page=dept/dialup