Re: find all directed paths between a source and destination

On Wednesday 09 April 2008 17:00, Ginu wrote:
Hello all. I have a graph (that is not necessarily directed) of a
number of nodes. I'm trying to enumerate through all directed paths
between source and destination (to avoid routing loops). There
shouldn't be an infinite number of solutions to this problem because
nodes cannot be traversed more than once in the solution. ... [PEB]

Your problem may be ill-formed, in that you can get different answers
depending on how you enumerate the paths.

The simple example I can think of has 4 nodes.
B
/|\
A | C
\|/
D
In text, A and C are source and destination. The edges are
(A, B)
(B, C)
(A, D)
(D, C)
(B, D)

If you choose A-B-D-C, you're done: just 1 path. But you can choose
A-B-C, then A-D-C, which gives 2 paths.

What answer do you want? 2 (maximum)? Or is either of 1 or 2
acceptable? Or are there other things that make the problem clearer?

-paul-
.

Relevant Pages