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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-09-19 01:53:16

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