[EM] Floyd-Warshall algorithm - variations

[Markus Schulze]

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