Re: [Boost-users] Using raph algorithm

From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-04-10 15:52:44

On Apr 10, 2006, at 6:40 AM, David Zweigenhaft wrote:

> Does anyone know how to achieve the following:
>
> find all the paths between 2 nodes ?

There's potentially an exponential number of these, assuming you  
ignore cycles. A naive algorithm would do a depth-first traversal  
from one of the nodes, recording paths along which the other node is  
found.

>         Or, find the first N shortest paths between 2 nodes ?

One could use this to
> find the shortest path using include/exclude constraints (passing  
> through list of nodes)
Excluding nodes is easy... you just don't allow the traversal to  
visit those nodes. Include constraints could get rather complicated  
quite quickly, although I imagine you might be able to start the  
traversal at one of the included nodes...
>
> BWY - am I using the correct mailing list ?

Yes.

        Doug