[EM] Floyd algorithm? - peace

[Stephane Rouillon]

Markus Schulze a écrit :

> Dear David,
>
> you wrote (18 Dec 2003):
> > I know a few 'shortest path' algorithm like "Dijkstra" and
> > "Bellman-Ford". Dijkstra is having an 0(n*Log(n)) complexity (in time)
> > and for the other... I don't remember but it is a more distributed
> > algorithm.

If I remember well one uses reaching to update labels the other pushing...
Am I right?

> Bellman-Ford, Dijkstra, and Floyd have the property that they all look
> for possible short cuts until a termination criterion is met. They differ
> only in the order in which the possible short cuts are considered.

I though that Floyd was an implementation of the maximum-flow problem,
which in my eye is not equivalent to a shortest path. The first is based on
capacities,
the other on costs...
But what do I know, I am just supposed to be a specialist in those matter,
I'm humble enough not to be sure.

> You wrote (18 Dec 2003):
> > Now sometime Markus talk about "strongest path" wich might be something
> > completely different.
>
> "Strongest paths" and "shortest paths" are mathematically equivalent in
> so far as both follow the same concept of short cuts. In the shortest
> path problem, a short cut is a situation with p_old[j,k] > p[j,i] + p[i,k]
> so that you can set p_new[j,k] = p[j,i] + p[i,k]. In the strongest path
> problem, a short cut is a situation with p_old[j,k] < min ( p[j,i], p[i,k] )
> so that you can set p_new[j,k] = min ( p[j,i], p[i,k] ).
>
> By the way: In the scientific literature, "strongest paths" are called
> "maximum capacity paths".

That's what I call a maximum-flow path. I never imagined that election method
would
bring me right back to my thesis... Maybe it is a sign it is time to finish it.

> Markus Schulze
> ----
> Election-methods mailing list - see http://electorama.com/em for list info

Steph