Douglas Gregor wrote:
On Sep 16, 2005, at 2:37 AM, Vladimir Prus wrote:
I'd like to extract all possible shortest path from a source to a destination... not only one path. Please, could you help me to resolve this problem?
Hi, I'm afraid BGL does not have such a algorithm at the moment.
One though that comes to me is the use another algorithm (not present in BGL, either), for finding k shortest paths. You'll then be getting next shortest path until the lengths are all the same.
Or, one can use Dijkstra's shortest paths algorithm with a custom visitor that accumulates predecessors in its edge_relaxed/ edge_not_relaxed events.
Yes, probably. For a DAG, you can run Dijkstra, and then traverse the graph from the end (sink) vertex, passining only along the edges that give the min path length. OTOH, such algorithm still has to be written, and one should consider what to do with cycles and so on... - Volodya