[EM] Floyd-Warshall algorithm - variations
Ernest Prabhakar
drernie at mac.com
Fri Dec 19 10:09:02 PST 2003
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
More information about the Election-Methods
mailing list