シュルツ方式
45人の投票者が5人の候補者 A, B, C, D, E を順位付けする下記の例を考えてみよう。
5 ACBED(5人の投票者がA > C > B > E > Dと選好することを表す。)
5 ADECB
8 BEDAC
3 CABED
7 CAEBD
2 CBADE
7 DCEBA
8 EBADC
初めにペアに関する選好を計算する。例えば A と B を比較すると、B より A を好む投票者が 5+5+3+7 = 20 人いて、A より B を好む投票者が 8+2+7+8 = 25 人いる。よって d[A,B] = 20, d[B,A] = 25 となる。ペアに関する選好の全体像は以下のようになる。
右の図式は、最強の道を視覚的に把握しやすくしたもので、X から Y への矢印に d[X,Y] の値を付した有向グラフである。d[X,Y] > d[Y,X] ならば、d[Y,X] の値は選挙の結果に影響を与えないため、図には d[X,Y] の値のみ記す。
道の強さが辺の強さの最小値であることを思い出そう。
シュルツ方式を実装するにあたって唯一困難な段階は、最強の道の強さを計算することである。しかし、これはwidest path problemと呼ばれるグラフ理論において良く知られた問題である。従って強さを計算する単純な一つの方法は、ワーシャル・フロイド法の変形である。下記の擬似コードは、アルゴリズムを表している。
このアルゴリズムは優れていて、候補者数をCとするとO(C)の時間計算量で解が求まる。(これにはd[*,*]を求める時間計算量を含んでおらず、最も簡単な方法で実装するなら、投票者の数をVとするとO(VC)の時間計算量が必要である。)