Re: [Boost-users] Find all the shortest path from a graph

On Sep 19, 2005, at 1:53 AM, Vladimir Prus wrote:

Douglas Gregor wrote:

...

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,

Yes, it would be a good addition.

and one should consider what to do with cycles and so on...

I'm not sure that cycles matter. Dijkstra's handles only non-negative edge weights to start with, so it's only zero-weight cycles that would cause a problem. Doug