[EM] Floyd algorithm? - peace
Markus Schulze
markus.schulze at alumni.tu-berlin.de
Thu Dec 18 14:44:06 PST 2003
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.
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.
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".
Markus Schulze
More information about the Election-Methods
mailing list