[EM] Beatpath Magnitude Algorithm Revision

[Markus Schulze]

Dear Mike,

beat-paths and Schwartz sets can be calculated by using the
Dijkstra algorithm or the Floyd algorithm.

******

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

Ouput:
"Schwartz[X] = true" means that candidate X is a Schwartz winner.
m1[X,Y] with X <> Y is the absolute strength of the beat-path
from candidate X to candidate Y.
m2[X,Y] with X <> Y is the margin of the beat-path from
candidate X to candidate Y.

******

Floyd Algorithm to calculate the Schwartz winners:

for i := 1 to NumberOfCandidates do
Schwartz[i] := true;

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i <> j)
   {
    if (d[i,j] > d[j,i]) then
    dummy[i,j] := true;
    else
    dummy[i,j] := false;
   }

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i <> j) then
for k := 1 to NumberOfCandidates do
if ((i <> k) and (j <> k)) then
if ((dummy[j,i] = true) and (dummy[i,k] = true)) then
dummy[j,k] := true;

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i <> j) then
if ((dummy[i,j] = false) and (dummy[j,i] = true)) then
Schwartz[i] := false;

******

Floyd Algorithm to calculate the beat-paths:

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

    m2[i,j] := d[i,j]-d[j,i];
   }

for i := 1 to NumberOfCandidates do
for j := 1 to NumberOfCandidates do
if (i <> j) then
for k := 1 to NumberOfCandidates do
if ((i <> k) and (j <> k)) then
   {
    s := MIN{m1[j,i],m1[i,k]};
    t := MIN{m2[j,i],m2[i,k]};
    if ((m1[j,k] < s)
       or ((m1[j,k] = s)
       and (m2[j,k] < t))) then
       {
        m1[j,k] := s;
        m2[j,k] := t;
       }
   }

******

The Dijkstra algorithm and the Floyd algorithm can be
found in every book about "Combinatorial Optimization"
or "Graph Theory."

Markus Schulze