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

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

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.

     Doug