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.

Download

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. 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. 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. 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.

    1. 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.

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

      1. 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. 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.

  3. 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. 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.

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

  5. I preferred your previous algorithm. It was better in that you were trying to find paths FROM a node TO another node. This is just going to find all legitimate paths FROM a node to a graph terminal vertex i.e. if we are trying to find all paths FROM a vertex TO another vertex, this algorithm will not satisfy it.

    1. It would be a small addition to add checking code to see if it satisfies the constraint. The previous code was more complex than necessary hence why I replaced it.

Leave a Reply

Your email address will not be published. Required fields are marked *