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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-09-19 09:38:16

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