[EM] Floyd-Warshall algorithm - variations

[Ernest Prabhakar]

Hi Andrew,

> The "Floyd algorithm" is usually called the Floyd-Warshall all-pairs 
> shortest
> path algorithm. This algorithm computes the cost of the "best path" in 
> a
> weighted, directed graph. The notion of 'best' and 'cost' are defined 
> by two
> operations we can call 'min' and '+', respectively....For example, if 
> we choose 'min' = min and '+' = +, then the cost of a path is the sum 
> of the weights of the edges and the algorithm finds the lowest-cost
> path. If we choose 'min' = max and '+' = min, then the cost of a path 
> is
> the lowest-weight edge and the algorithm finds the highest-weight path.

Thanks - this is awesome.  I think this highlights my biggest question 
about the Schulze method.  Essentially, Markus (and Mike) are 
recommending we treat the pairwise matrix of votes as defining a graph, 
where each candidate is a node and each vote count is a directed edge 
between two nodes.  This allows us to use standard mathematical 
techniques for traversing the graph, i.e., calculating the relative 
'strength' of two candidates.  Yes, Stef, time to finish that thesis, 
all this math really is the same.

Even if we agree to use a graph, and a particular graph-traversal 
algorithm, there's still a couple different ways to do the counting 
(i.e., to define the 'best' path we're searching for).

a) Use of 'shortest' path vs. 'strongest'

This is the issue you raise below:  do we add the paths along the way 
to get the 'length' of the path, or do we pick the 'weakest link' to 
measure the strength of path?

b) Use of relative wins vs. absolute votes

Do we count -all- the votes of A over B (A/B), or just net votes (A/B - 
B/A).

 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

These appear to be fundamental differences, independent of whether you 
use Floyd-Warshall or Dijkstra (or even when you can spell any of their 
names correctly, which I can't :-) for graph traversal.  That is, 
beatpath explicitly uses a slightly different set of assumptions than 
those used in the formal Schulze method.

Does anyone know if they're equivalent, or have any reason to argue 
(non-insultingly, please!) that one is better than the other?

-- Ernie P.


On Dec 19, 2003, at 8:02 AM, Andrew Myers wrote:

> Hi all,
>
> The "Floyd algorithm" is usually called the Floyd-Warshall all-pairs 
> shortest
> path algorithm. This algorithm computes the cost of the "best path" in 
> a
> weighted, directed graph. The notion of 'best' and 'cost' are defined 
> by two
> operations we can call 'min' and '+', respectively. As long as the 
> actual
> mathematical operations have the right algebraic properties, the 
> algorithm will
> work. The core of the algorithm updates the matrix as follows:
>
>     m[i][j] = 'min'(m[i][j], m[i][k] '+' m[k][j])
>
> For example, if we choose 'min' = min and '+' = +, then the cost of a 
> path
> is the sum of the weights of the edges and the algorithm finds the 
> lowest-cost
> path.
>
> If we choose 'min' = max and '+' = min, then the cost of a path is
> the lowest-weight edge and the algorithm finds the highest-weight path.
> This is the particular choice of operators that results in selecting
> the beatpath winner.
>
> Many other choices for 'min' and '+' are possible, of course.
>
> When implemented correctly it has O(V^3) running time where V is the 
> number of
> vertices (nodes) in the graph.
>
> -- Andrew Myers
> ----
> Election-methods mailing list - see http://electorama.com/em for list 
> info