# [EM] Algorithm to Calculate the Schwartz Set

Markus Schulze markus.schulze at alumni.tu-berlin.de
Sun Jan 11 03:22:02 PST 2004

```Hallo,

the Schwartz set can be calculated with the Floyd algorithm
in a runtime of O(N^3), where N is the number of candidates.
It cannot be said frequently enough that the order of the
indices in the triple-loop of the Floyd algorithm is _not_
irrelevant.

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

Output: "Schwartz[i] : = true" means that candidate i is
a Schwartz winner.
"Schwartz[i] : = false" means that candidate i is not
a Schwartz 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
p[i,j] : = true ;
if ( d[i,j] <= d[j,i] ) then
p[i,j] : = false ;
}

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

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

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

Markus Schulze

```