[EM] Floyd-Warshall algorithm - variations

[Ernest Prabhakar]

On Dec 19, 2003, at 11:30 AM, Markus Schulze wrote:
> We both are recommending strongest paths and absolute votes. There
> is absolutely no difference between Mike's and my recommendation.

Ah, thank you!  Sorry, I got confused between what you each recommended 
and what I was reading about the various algorithms.

I actually find the Floyd algorithm confusing, with all the indices.   
I think Dijkstra is not only clearer, but easier to implement using 
objects.  Here's some pseudo-Python code I've been working on, which I 
think implements the Schulze method via Dijkstra.

The main object is a 'Candidate (start, current, or beat) with the 
following fields:
- beats[] # list of candidates this one has beaten
- votes{} # dictionary of votes for this one against each other 
candidate
- strength # hold temporary path strengths; allows sorting to find 
'smallest'

def FindStrongestPaths(start):
"Find best paths to all candidates starting from candidate 'start'"
final = []
start.strength = HUGE_VAL # arbitrarily large, so anything is 'min' 
relative to it
unchecked = [start]
while (current = unchecked.smallest()): # removes and returns smallest 
elements
   final.append(current)
   for beat in current.beats: # loop over candidate current has beaten 
(i.e., neighbor nodes)
      strength = min(current.strength, current.votes[beat])
      if not final.contains(beat) and (not unchecked.contains(beat) or 
strength > beat.strength):
        beat.strength = strength
        if not unchecked.contains(beat): unchecked.append(beat)
     #endif
   #end for
#end while
#end def


Anyone care to check it for me (yes, I know its not legal python; done 
for clarity; I'm asking about the algorithm).

-- Ernie P.