about multiple path

[asif_rahman0]

Can anyone tell me that how can i compute the multiple length(same) of a shortest path and also where i want to know the both path or vertex number??

Is it possible to find out with Floyd Warshall algo or any other algorithm??

please help me.

[rmotome]

You can choose any shortest path algorithm so long as you compute the predecessor matrix/array. Then remove the shortest path and run the algorithm once more; you will end up with the alternate shortest path. If you find a way of computing all (same length) shortest paths with a single pass of the shortest path algorithm let me know.

[mf]

Let dist(x) be the length of shortest path from the source to vertex x.
Remove all (directed) edges (u,v) from the graph for which: dist(v) != weight(u,v) + dist(u).
Now, all remaining paths from source to destination are shortest paths.

Edit:
Yes, that dist(v) was a typo. Fixed now.

[asif_rahman0]

thnx rmotome and mf.
Now i got it. But to mf,

Code: Select all

dist(v) != weight(u,v) + dist(v)

i dont get this line. Is it dist(v) != weight(u,v) + dist(u) or not?

mf, if i consider graph as an undirected then what should be the step??

[mf]

Just consider each undirected edge as two directed edges of the same weight and opposite orientation.

[asif_rahman0]

thank you mf. now i can solve the 10354:).