[EM] Floyd-Warshall algorithm - variations

[Ernest Prabhakar]

On Dec 19, 2003, at 3:02 PM, Markus Schulze wrote:

> Dear Ernest,

Hi Markus,

Thanks for the prompt reply.
>
> I don't know Python-ish pseudo-code.

I'll try to find ways to make it more English-like, so the algorithm is 
clearer.

> But in Pascal/C-ish pseudo-code
> the Dijkstra algorithm (aka Dykstra algorithm) looks as follows when
> the strength of a pairwise defeat is measured primarily by p1 (= the
> absolute number of votes for the winner of this pairwise defeat) and
> secondarily by p2 (= the margin of this pairwise defeat):

<lots of code omitted>
Ouch.  That's why I no longer program in C (or procedural languages). 
:-)

Let me put it another way.   Could you please explain in words why you 
feel it is necessary or useful to use *both* absolute votes and margins 
in the calculation?   Are the margins used simply to break a tie 
between absolute votes?  I think that's what is implied by the line:
>            if ( p1[i,x] = d1[x,k] ) then
>            t : = min { p2[i,x], d2[x,k] } ;

Also, is there a particular mathematical or anti-strategic reason for 
randomizing the tie-breaking round, rather than just automatically 
picking the candidate who would have the best chance of winning such a 
random draw?

-- Ernie P.