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.

Answer 2

As this is a DAG you can topologically sort the nodes in O(V+E) time. Let's assume the source vertex is S. Then from S start traversing the nodes in depth first fashion. When we're processing node U , let's assume there's an edge U->V then V is of course not yet visited (why? because it's an directed acyclic graph) So you can reach from S to V via node U in d[U] ways where d[U] is the number of paths from S to U.

So number of paths from S to any node V, d[V] = d[x1]+d[x2]+d[x3]+ . . . +d[xy], where there are edge like x1->V, x2->V, . . . xy->V

This algorithm will take O(V+E) to topologically sort the graph and then for calculating number of paths at most O(V*E ). You can further reduce its run time of calculating number of path to O(V+E) using adjacency list instead of adjacency matrix and this is the most efficient solution so far.

Answer 3

Assume G(V,E)
Let d[i][j] = the number of all the paths from i to j
Then d[i][j]= sigma d[next][j] for all (i,next) in E

It seems too slow? Okay. Just memorise it(some guys call it dynamic programming). Like this

memset(d,-1,sizeof(d))// set all of elements of array d to -1 at the very beginning
saya(int i,int j)
{
    if (d[i][j]!=-1) return d[i][j];//d[i][j] has been calculated
    if (i==j) return d[i][j]=1;//trivival cases
    d[i][j]=0;
    for e in i.edges
        d[i][j]+=saya(e.next,j);
    return d[i][j];
}

Now saya(i,j) will return the number of all the paths from i to j.