Page 1 of 1
about multiple path
Posted: Fri Jul 21, 2006 9:56 pm
by 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.
Here is my approach
Posted: Sun Jul 23, 2006 3:28 pm
by 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.
Posted: Sun Jul 23, 2006 3:41 pm
by 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.
Posted: Sun Jul 23, 2006 9:21 pm
by asif_rahman0
thnx rmotome and mf.
Now i got it. But to mf,
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??
Posted: Sun Jul 23, 2006 10:03 pm
by mf
Just consider each undirected edge as two directed edges of the same weight and opposite orientation.
Posted: Mon Jul 24, 2006 5:09 pm
by asif_rahman0
thank you mf. now i can solve the 10354:).