# Beat-Path algorithm

Blake Cretney bcretney at my-dejanews.com
Tue Sep 29 15:24:57 PDT 1998

```Here is my attempt at an algorithm for calculating the best beat
path values, as used in methods such as Schulze.
I am assuming this is still an open question.

margins of victory, or the number of votes on the winning side,
depending on your point of view.  Both should have MAXVALUE along
the i=j diagonal.

I have presented it as a C code fragment.

dirty=1;
while(dirty) { /* check if change made */
dirty=0;
for(i=0;i<n;i++) { /* each row */
for(j=0;j<n;j++) { /* each column */
for(k=0;k<n;k++) { /* column in corresponding
candidate's row */
int s=min(M[i][j],M[j][k]);
/* combined path has the
minimum strength of its
components */
if(s>M[i][k]) { /* found a better path */
M[i][k]=s;
dirty=1;
}
}
}
}
}

The idea is simply to find obvious beat-path improvements until
M holds the best beat paths.

This is a polynomial-time algorithm since
1.  The for loops all have polynomial bounds
2.  The while loop can only continue as changes are made
There are only n^2 cells, and they can only be changed to greater
values existing in the matrix.  Since there can only be n^2 such
values, n^4 is an obvious upper bound for the while loop.

So, the whole thing is polynomial-time.

-----== Sent via Deja News, The Discussion Network ==-----