# [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
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