슐츠 방법

슐츠 방법(Schulze method)은 1997년 마커스 슐츠가 개발한 선거 제도이다. 이 방법으로 승자들의 정렬된 목록을 만들어낼 수 있다.

예시 
후보자가 5명(A, B, C, D, E)이고 투표자가 45명인 예시를 살펴보자.

짝 대결 그래프

경로의 강도(strength)는 가장 약한 고리(=노드)의 강도를 말한다.
다음 표는 후보자 각 쌍에 대해 한 후보자 X에서 다른 후보자 Y로 가는 최강 경로를 보여준다.
이들 최강경로에서 가장 약한 고리는 밑줄로 표시되어 있다.

E 후보자는, 모든 다른 후보자 X에 대하여 p[E,X] ≥ p[X,E]이므로 잠재적 승자이다.
 25 = p[E,A] > p[A,E] = 24이므로 후보자 E는 후보자 A보다 선호된다.
 28 = p[E,B] > p[B,E] = 24이므로 후보자 E는 후보자 B보다 선호된다.
 28 = p[E,C] > p[C,E] = 24이므로 후보자 E는 후보자 C보다 선호된다.
 31 = p[E,D] > p[D,E] = 24이므로 후보자 E는 후보자 D보다 선호된다.
 28 = p[A,B] > p[B,A] = 25이므로 후보자 A는 후보자 B보다 선호된다.
 28 = p[A,C] > p[C,A] = 25이므로 후보자 A는 후보자 C보다 선호된다.
 30 = p[A,D] > p[D,A] = 25이므로 후보자 A는 후보자 D보다 선호된다.
 29 = p[C,B] > p[B,C] = 28이므로 후보자 C는 후보자 B보다 선호된다.
 29 = p[C,D] > p[D,C] = 28이므로 후보자 C는 후보자 D보다 선호된다.
 33 = p[B,D] > p[D,B] = 28이므로 후보자 B는 후보자 D보다 선호된다.
그러므로 슐츠 순위는 E > A > C > B > D 순이다.

구현 
후보자 수를 C라고 하자.
그러면 플로이드-워셜 알고리듬으로 가장 강력한 경로의 강도를 계산할 수 있다.
아래의 파스칼 유사코드는 그러한 경로 판단을 나타낸 것이다.

 입력: d[i,j]는 i후보를 j후보보다 강력하게 선호하는 투표자 수이다.
 출력: p[i,j]는 i후보에서 j후보로 가는 가장 강력한 경로의 강도이다.

for i : = 1 to C
begin
   for j : = 1 to C
   begin
      if ( i ≠ j ) then
      begin
         if ( d[i,j] > d[j,i] ) then
         begin
            p[i,j] : = d[i,j]
         end
         else
         begin
            p[i,j] : = 0
         end
      end
   end
end

for i : = 1 to C
begin
   for j : = 1 to C
   begin
      if ( i ≠ j ) then
      begin
         for k : = 1 to C
         begin
            if ( i ≠ k ) then
            begin
               if ( j ≠ k ) then
               begin
                  p[j,k] : = max ( p[j,k], min ( p[j,i], p[i,k] ) )
               end
            end
         end
      end
   end
end

외부 링크 
 

선거 제도