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 ?
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 ?
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
One could use this to traversal at one of the included nodes...
BWY - am I using the correct mailing list ?
Yes. Doug
participants (2)
-
David Zweigenhaft -
Doug Gregor