Beat-Path algorithm

[Blake Cretney]

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.

Start with a matrix M[n][n] This matrix should either have the
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 ==-----
http://www.dejanews.com/  Easy access to 50,000+ discussion forums