[EM] Floyd algorithm? - peace

[Markus Schulze]

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