[EM] Floyd-Warshall algorithm - variations

[Andrew Myers]

On Fri, Dec 19, 2003 at 10:08:02AM -0800, Ernest Prabhakar wrote:
> From looking at their math, it appears that Markus ("Schulze method") 
> is recommending:
> a) shortest path
> b) relative wins
> 
> while Mike ("beatpath") is recommending:
> a) strongest path
> b) absolute votes

As I understand it, they are both computing beatpath winners where
the goal is to find the strongest path using absolute votes.
The difference is that Markus is building on a more efficient algorithm,
the classic Floyd-Warshall algorithm. The key is to get the order
of the nested loops right so the algorithm converges in one pass.
This makes the algorithm simpler and asymptotically faster.
It is a dynamic programming algorithm; see any good algorithms
textbook (e.g., Cormen, Leiserson, and Rivest) for more details.

Unless there are a lot of candidates, it probably doesn't matter
much which algorithm is used.

-- Andrew Myers