15

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?

Derek O
  • 16,770
  • 4
  • 24
  • 43
Saiiiira
  • 191
  • 1
  • 1
  • 4

3 Answers3

29

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

Jeremiah Willcock
  • 30,161
  • 7
  • 76
  • 78
  • But how to keep a count of the number of paths from each vertex to target? E.g., if any ith vertex in the DAG has a direct connection to the target, we know that there is a connection, so we increment the counter. But ith vertex might have many other vertexes which, in their turn can have either explicitly or implicitly connected to the target. So how to handle this part? What will be the running time? – David Hovsepyan Nov 13 '22 at 23:03
11

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.

stalker
  • 1,300
  • 1
  • 13
  • 16
2

This question has been asked elsewhere on SO, but nowhere has the simpler solution of using DFS + DP been mentioned; all solutions seem to use topological sorting. The simpler solution goes like this (paths from s to t):

Add a field to the vertex representation to hold an integer count. Initially, set vertex t’s count to 1 and other vertices’ count to 0. Start running DFS with s as the start vertex. When t is discovered, it should be immediately marked as finished (BLACK), without further processing starting from it. Subsequently, each time DFS finishes a vertex v, set v’s count to the sum of the counts of all vertices adjacent to v. When DFS finishes vertex s, stop and return the count computed for s. The time complexity of this solution is O(V+E).

Pseudo-code:

simple_path (s, t) 
    if (s == t) 
        return 1 
    else if (path_count != NULL)
        return path_count 
    else 
        path_count = 0
        for each node w ϵ adj[s] 
            do path_count = path_count + simple_path(w, t) 
        end 
    return path_count 
end
Shivam
  • 69
  • 4