# [EM] Floyd-Warshall algorithm - variations

Ernest Prabhakar drernie at mac.com
Fri Dec 19 12:06:39 PST 2003

```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.

```

More information about the Election-Methods mailing list