Re: find all directed paths between a source and destination
- From: Ginu <osheikh81@xxxxxxxxx>
- Date: Tue, 15 Apr 2008 09:06:46 -0700 (PDT)
On Apr 11, 12:30 pm, "Paul E. Black" <p.bl...@xxxxxxx> wrote:
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-
Thanks for the responses. Essentially I would like to determine all
directed paths between A and C, so all three that you suggested. I
then have an optimization function to select one above the others.
.
- References:
- find all directed paths between a source and destination
- From: Ginu
- Re: find all directed paths between a source and destination
- From: Paul E. Black
- find all directed paths between a source and destination
- Prev by Date: Re: How can I tell if F is a string or if it is a number?
- Next by Date: Re: How can I tell if F is a string or if it is a number?
- Previous by thread: Re: find all directed paths between a source and destination
- Next by thread: Sorted heap trees
- Index(es):
Relevant Pages
|
