# [EM] Floyd-Warshall algorithm - variations

Markus Schulze markus.schulze at alumni.tu-berlin.de
Fri Dec 19 15:07:01 PST 2003

```Dear Ernest,

I don't know Python-ish pseudo-code. 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):

***

N is the number of candidates.

Input: d[i,j] with i <> j is the number of voters who strictly prefer
candidate i to candidate j.

Output: "w[i] = true" means that candidate i is a potential winner.
"w[i] = false" means that candidate i is not a potential winner.

***

for i : = 1 to N do
for j : = 1 to N do
if ( i <> j ) then
{
if ( d[i,j] > d[j,i] ) then
d1[i,j] : = d[i,j] ;
if ( d[i,j] <= d[j,i] ) then
d1[i,j] : = -1 ;

d2[i,j] : = d[i,j] - d[j,i] ;

p1[i,j] : = d1[i,j] ;
p2[i,j] : = d2[i,j] ;
}

for i : = 1 to N do
{
for j : = 1 to N do
unchecked[j] : = true ;

unchecked[i] : = false ;

for j : = 2 to N do
{
v : = - MAXINT ;
w : = - MAXINT ;
x : = 0 ;

for k : = 1 to N do
if ( unchecked[k] = true ) then
if (( p1[i,k] > v ) or (( p1[i,k] = v ) and ( p2[i,k] > w ))) then
{
v : = p1[i,k] ;
w : = p2[i,k] ;
x : = k ;
}

unchecked[x] : = false ;

for k : = 1 to N do
if ( unchecked[k] = true ) then
{
s : = min { p1[i,x], d1[x,k] } ;
if ( p1[i,x] < d1[x,k] ) then
t : = p2[i,x] ;
if ( p1[i,x] > d1[x,k] ) then
t : = d2[x,k] ;
if ( p1[i,x] = d1[x,k] ) then
t : = min { p2[i,x], d2[x,k] } ;

if (( p1[i,k] < s ) or
(( p1[i,k] = s ) and ( p2[i,k] < t ))) then
{
p1[i,k] : = s ;
p2[i,k] : = t ;
}
}
}
}

for i : = 1 to N do
{
w[i] : = true ;
for j : = 1 to N do
if ( i <> j ) then
if (( p1[j,i] > p1[i,j] ) or
(( p1[j,i] = p1[i,j] ) and ( p2[j,i] > p2[i,j] ))) then
w[i] : = false ;
}

Markus Schulze

```