# Finding all paths in a Directed Acyclic Graph (DAG)

Finding all paths on a Directed Acyclic Graph (DAG) seems like a very common task that one might want to do, yet for some reason I had trouble finding information on the topic (as of writing, Sep 2011). The best Google result I found on this topic was at Stackoverflow, but surprisingly very few posts or answers even. So I decided to roll out my own implementation, because that’s the way I roll. I bet some astute reader out there will no doubt point to me the original implementation that I duplicated.

I’ve wiped out my original post because I realised how convoluted my initial approach was. The new code is much simpler, so simple that I’m hoping it’s self explanatory enough that I won’t even have to write up a detail blog about it. But if you need some clarification post a comment below.

Some actual C++ code for the given example can be downloaded here FindAllPathsInDAG.cpp (right click and Save As)

## 18 thoughts on “Finding all paths in a Directed Acyclic Graph (DAG)”

1. robert says:

It seems like your example code is shown as html template. there is a big mass.

2. robert says:

It helps too much, thanks.

3. Thanks for the help. I probably could have found it my-self, but I would not have consider computing all path as a option without reading your post.
What would you say is the complexity of this algorithm? I can see that the number of path is equal to the sum of (the number of out-edges per node-1) – btw it could be worst stating it in the post. Lets call this number N_out. The worst case complexity is thus N_out*(number of nodes), but that’s only if the first nodes as N_out edges to the second.
But what would be the average complexity with respect to average number of out-edges ?

1. nghiaho12 says:

I believe the algorithm is linear in complexity since it visits every node once. It is very similar to the Breadth first search algorithm.

1. I actually said something wrong about the number of path, because I it looked like a BFS (more like a DFS no?). But actually it is (possibly) much more: edges can be parsed several times as edge (1,0) in your example.
The simplicity of the algorithm made me lost track of it…

1. celina says:

I believe the complexity is linear to the number of paths, but exponential on the number of links and nodes. In the worst case scenario, you can have 2 exp (n-1) paths given you have n nodes.

4. kartik t s says:

Th algorithm doesn’t work if there are more than one end state

1. nghiaho12 says:

I didn’t consider that scenario. A cheat way to make it work would be to add an extra “dummy” node that joins all your end states together.

5. Hoda says:

How we can run this algorithm in matlab?I mean what is matlab code for it?
I really need it ASAP,pls help.

1. nghiaho12 says:

This code has no way of running in Matlab.

1. Hoda says:

Are u sure about that,it’s alittle strange, Do u mean there is no way to find all possible paths in a DAG in matlab?why?If there is an algorithm,it should work in every programming enviroment,isn’t it?
Anyway,What should I do?
I heard it’s solved by DFS or BFS in matlab,but I don’t know how?

1. Hoda says:

Oh,sure,C++ code will not work in Matlab, Unfortunately I don;t know c++:(
tanx for the link,but it doesn’t consider the direction
eg.I have 4 nodes{1,2,3,4)and edges are as below:(1,2);(1,3);(2,3);(2,4);(3,4); if I want to have all possible paths from 1 to 4,it should be:1-2-4;1-2-3-4;1-3-4
but when I use the function in the link that u commented,the paths are such:1-2-4;1-2-3-4;1-3-4;1-3-2-4
last path (1-3-2-4)is not possible,because there is no edge from 3 to 2.

6. Hoda says:

I solved the problem,it was because of adjancy matrix,Now,as mentioned in the site;The main Limitation of this function is that, as the total number of node increases, the execution time also increases. The total number of nodes is also limited to 20, due to memory considerations.Pls let me know if u have any comments about that.tnx

1. nghiaho12 says:

I haven’t personally used that code but I find it very odd it is limited to 20. 20 doesn’t seem like it’ll use that much memory … I would try increasing it and see how it goes.

7. Hoda says:

It’s best kind of u,this problem confused me for several weeks and I really need it ASAP.