DP on DAGs: Counting Paths

1. Formulating the Path Counting Problem with DP

Let's consider a DAG, a source vertex s, and a destination vertex t. Our goal is to find the number of unique paths from s to t.

A brute-force approach might involve a DFS from s that explores every possible path, incrementing a counter whenever t is reached. However, this is highly inefficient. Many paths might converge on the same intermediate vertex, and we would repeatedly recompute the number of paths from that vertex to the destination. This hints at the two properties you learned about in our DP module:

• Optimal Substructure: The total number of paths to a vertex v can be expressed in terms of the number of paths to its immediate predecessors.
• Overlapping Subproblems: The number of paths to a particular vertex u will be needed to calculate the path counts for all vertices that u points to.

This structure is ideal for dynamic programming. Let's define our DP state:
dp[u] = The number of distinct paths from the source s to vertex u.

Our goal is to compute dp[t].

The recurrence relation follows directly from this definition. Any path from s to a vertex v must pass through one of its immediate predecessors. Therefore, the total number of paths to v is the sum of the paths to all its predecessors.

The base case for this recurrence is dp[s] = 1, signifying one path from s to itself (an empty path). All other dp values are initialized to 0.

The following resource provides a formal introduction to this concept.

2. The Power of Topological Sort for DP on DAGs

The recurrence dp[v] = Σ dp[u] has a crucial dependency: to calculate dp[v], we must have already computed the final values of dp[u] for all predecessors u of v.

How can we guarantee this? This is precisely what a topological sort provides! By processing the vertices of the DAG in a topologically sorted order, we ensure that by the time we consider any vertex v, we have already processed all vertices u that have a path to v. This means their dp values have already been finalized.

This allows us to turn the recursive DP formulation into a simple, iterative (tabulation-based) algorithm.

The Algorithm:

1. Topological Sort: Compute a topological ordering of the graph's vertices. Kahn's algorithm is a natural fit here as it's already iterative.
2. Initialization: Create a dp array of size V and initialize all its values to 0. Set dp[source] = 1.
3. Iterate and Calculate: Traverse the vertices in the topological order you found. For each vertex u:
   • For each of its neighbors v:
     • Add the number of paths to u to the number of paths to v: dp[v] = dp[v] + dp[u].
4. Result: After iterating through all vertices, the value dp[destination] will hold the total number of distinct paths from s to t.

Let's walk through an example. Consider the graph from the GeeksforGeeks article with V=4, src=2, dest=3, and edges [[0,1], [0,3], [2,0], [2,1], [1,3]].

• Topological Sort (Kahn's):
  • In-degrees: in[0]=1, in[1]=2, in[2]=0, in[3]=2.
  • Queue q starts with [2].
  • Topological order will be [2, 0, 1, 3].
• DP Calculation:
  1. Initialize dp = [0, 0, 0, 0]. Set dp[src], so dp[2]=1.
     dp is now [0, 0, 1, 0].
  2. Process u=2 from topo order. Neighbors are 0 and 1.
     • dp[0] += dp[2] => dp[0] = 1.
     • dp[1] += dp[2] => dp[1] = 1.
     • dp is now [1, 1, 1, 0].
  3. Process u=0 from topo order. Neighbors are 1 and 3.
     • dp[1] += dp[0] => dp[1] = 1 + 1 = 2.
     • dp[3] += dp[0] => dp[3] = 1.
     • dp is now [1, 2, 1, 1].
  4. Process u=1 from topo order. Neighbor is 3.
     • dp[3] += dp[1] => dp[3] = 1 + 2 = 3.
     • dp is now [1, 2, 1, 3].
  5. Process u=3. No outgoing edges.
• Final Answer: dp[dest] = dp[3] = 3.

3. Implementation and an Alternative View

The iterative approach using topological sort is a clean and efficient way to implement this DP. The following resource provides an excellent C++ implementation.

Alternative: Top-Down DP with Memoization

As you know from our DP module, any problem solvable with tabulation can also be solved with memoization. This problem is no exception. We can write a recursive function, say count(u), that computes the number of paths from u to the destination t.

• Base Case: If u == t, we've found a path, so return 1.
• Memoization: If we've already computed count(u), return the stored value.
• Recursive Step: Otherwise, initialize a counter to 0. For every neighbor v of u, recursively call count(v) and add the result to the counter.
• Store and Return: Store the final count in our memoization table and return it.

The initial call would be count(source). Notice that this approach doesn't require us to compute a topological sort upfront. The call stack of the recursion implicitly handles the dependency order. A call to count(u) will only return after all count(v) for its successors have returned, which is essentially a post-order traversal, mirroring the logic of our DFS-based topological sort.

You can find a clear implementation of this approach in the same article.

Both the tabulation and memoization approaches have the same time complexity of $O(V+E)$ and space complexity of $O(V+E)$ (for the graph) plus $O(V)$ (for the dp/memo array and queue/recursion stack). In competitive programming, the iterative (tabulation) approach is often preferred for its lack of recursion overhead, but both are fundamentally equivalent and equally correct.

Conclusion

In this lesson, you've combined your knowledge of dynamic programming and graph traversal into a powerful pattern for solving problems on DAGs. This is a significant step, as many complex problems can be modeled as finding optimal values over a set of dependencies represented by a DAG.

Key Takeaways:

• Counting paths in a DAG exhibits optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming.
• The DP recurrence for counting paths to a vertex v is the sum of the path counts to its predecessors: dp[v] = Σ dp[u].
• A topological sort provides a linear ordering of vertices that guarantees that when we compute dp[v], the values for all its predecessors have already been finalized.
• This leads to an efficient $O(V+E)$ iterative algorithm using tabulation.
• An equivalent top-down recursive solution with memoization is also possible and often intuitive to formulate.

This pattern of using a topological sort to define an evaluation order for a DP recurrence is not limited to counting paths. In our next lesson, we will adapt this exact same technique to solve another fundamental problem: finding the shortest paths from a source in a weighted DAG.