Using raph algorithm

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Using raph algorithm

David Zweigenhaft
Does anyone know how to achieve the following:
 
  • find all the paths between 2 nodes ?
        Or, find the first N shortest paths between 2 nodes ?
  • find the shortest path using include/exclude constraints (passing through list of nodes)
 
BWY - am I using the correct mailing list ?

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Using raph algorithm

Doug Gregor-2

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

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users