0

I have a directed graph with a special root node from which all other nodes are reachable.

It is quite easy to find an arbitrary algorithm to find all pathes from a giving node to the root, for example this solution (DFS) using LinkedHashSets.

Well, this algorithm works well for small graphs but with larger graphs it doesn't come to an end in a reasonable amount of time.

My example graph has 129 nodes and 200 edges. In my eyes not an extremly HUGE graph...

Can somebody give me a hint how to solve this problem efficiently?

Maybe we can make use of other properties of my graphs. They all are:

  • connected
  • directed with loops
  • have a designated starting node
  • have a designated end node
Community
  • 1
  • 1
Klaus Schulz
  • 527
  • 1
  • 5
  • 20
  • 1
    Have you tried dijsktra alghoritem? – Jure Dec 08 '14 at 08:57
  • 1
    DFS is O(n), it's not clear that you can do better than that... – Oliver Charlesworth Dec 08 '14 at 08:58
  • I dont think you can find anything much better than dfs, but look here http://stackoverflow.com/questions/26857842/find-shortest-path/26858645#26858645 – Lrrr Dec 08 '14 at 09:09
  • In case you don't get your answer here, ask the question again at http://math.stackexchange.com/ - they can suggest you an algorithm and then you can try to implement it yourself and ask Stack Overflow for help. – spoko Dec 08 '14 at 09:22
  • @OliverCharlesworth Discovery of nodes is `O(n)`, trying to find all different paths using DFS is not that simple, you are going to revisit "closed" nodes, since you need to create ALL paths. – amit Dec 08 '14 at 09:25
  • @Jure Dijkstra's algorithm has nothing to do with that problem, Dijkstra is finding shortest path from a single source, it does NOT find all paths, this is not the shortest path problem here. – amit Dec 08 '14 at 09:26
  • @amit: If the goal is to find all the paths, then I totally agree. The title of this question implies a single path, though... – Oliver Charlesworth Dec 08 '14 at 11:26

1 Answers1

3

Well, not really - you cannot make it significantly more efficient, because the output size itself is huge. The number of paths is exponential in the number of nodes, have a look at this simple example:

V = {a, b, c}, E = {(a,b), (a,c), (b,c)}

This looks pretty simple, there are "only" 2 none trivial paths in the graph leading to c. a->c, a->b->c.

Now, consider adding a node d with edges (d,a), (d,b) - you will have 3 paths leading to c from the new root, d->a->b->c, d->a->c, d->b->c, still not too bad, but notice what happens when adding e with (e,d),(e,a), you will get one "family" of paths starting with e->d (3 above paths), and in addition, "family" of paths starting with "e->a" (2 paths). totaling in 5 paths. By repeating the process, you will get another two families, one with 5 paths, and the other with 3 paths. You probably start to understand that if you repeat the process k times, you will get #fibo(k) different paths, but the fibonacci number is very, very big for inputs such as 100 (~354*10^20, and keeps growing fast).

Thus, whatever you do - finding all paths in a graph is going to be inefficient, except for some "easy" graphs, such as trees.

tl;dr:
There are exponential number of paths leading to your target node, and finding all of them takes exponential time. DFS is a solid solution for this problem.

amit
  • 175,853
  • 27
  • 231
  • 333