Number of paths between two nodes in a DAG

问题:

I want to find number of paths between two nodes in a DAG. O(V^2) and O(V+E) are acceptable.

O(V+E) reminds me to somehow use BFS or DFS but I don't know how. Can somebody help?

回答1:

Do a topological sort of the DAG, then scan the vertices from the target backwards to the source. For each vertex v, keep a count of the number of paths from v to the target. When you get to the source, the value of that count is the answer. That is O(V+E).

回答2:

The number of distinct paths from node u to v is the sum of distinct paths from nodes x to v, where x is a direct descendant of u.

Store the number of paths to target node v for each node (temporary set to 0), go from v (here the value is 1) using opposite orientation and recompute this value for each node (sum the value of all descendants) until you reach u.

If you process the nodes in topological order (again opposite orientation) you are guaranteed that all direct descendants are already computed when you visit given node.

Hope it helps.