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