Count paths with Topological Sort

Question

I have a DAG and I need to count all the paths since any node to another node, I've researched a little bit and I found that it could be done with some Topological Order, but so far the solutions are incomplete or wrong.

So how is the correct way to do it?.

Thanks.

Answer 1

You can use recursion to count all of the paths in a tree/DAG. Here is the pseudocode:

function numPaths(node1, node2):
    // base case, one path from node to itself
    if (node1 == node2): return 1

    totalPaths = 0
    for edge in node1.edges:
        nextNode = edge.destinationNode
        totalPaths += numPaths(nextNode, node2)

    return totalPaths

Edit: A good dynamic approach to this problem is the Floyd-Warshall algorithm.