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...