0

Possible Duplicate:
Find the paths between two given nodes?

Given a directed graph, how to find ALL the possible paths between two nodes and return those paths.

If not in Java, please recommend me with the algorithm for it. I searched and what I found is using BFS or DFS, but I'm not able to see which is better in my case. And how to keep track of all paths not only the shortest one.

For example, given the following graph:

1 -> 2

1 -> 3

2 -> 3

3 -> 4

For paths between nodes 1 and 4, the output should be:

First Path: 1 -> 2 -> 3 -> 4

Second Path: 1 -> 3 -> 4

Community
  • 1
  • 1
user1899713
  • 85
  • 2
  • 7
  • 14
  • 1
    What do you want to do about cycles? There can be an infinity of paths between two nodes. For instance, given the graph 1→2, 2→3, 3→1, the paths from 1 to 3 include 1→2→3, 1→2→3→1→2→3, etc. – Ted Hopp Dec 13 '12 at 03:38
  • Interesting, that would be another problem. How to deal with this? – user1899713 Dec 13 '12 at 03:53
  • Have an array or create a wrapper that would store whether a mode is visited or not. – user892871 Oct 09 '14 at 17:52
  • see the Depth-first search Algorithme http://en.wikipedia.org/wiki/Depth-first_search – Walllzzz Dec 13 '12 at 03:33

1 Answers1

2

To me, backward traversal is much easier. Algorithm steps as below:

  1. Start from destination (i.e. 4 in your example) as starting point.
  2. Collect all nodes which has second element as destination e.g. (3,4).
  3. Assume starting point (3 in first iteration) as new destination and repeat steps 1 & 2 until there is no matching node available. Good scenario of recursion. You will get your collection as: [(1,2), (2,3), (3,4)], [(1,3), (3,4)]
  4. Check the collection created above and if the reverse destination is equal to your source then keep it otherwise discard (in your case, there is nothing to discard). YOU ARE DONE.
Yogendra Singh
  • 33,927
  • 6
  • 63
  • 73