DP on DAGs: Topological Sort Applications

1. The Core Principle: Dynamic Programming on a DAG

In previous DP problems, we often built up a solution in a table, say from dp[0] up to dp[n]. The key was that to compute dp[i], we relied on solutions to smaller subproblems (e.g., dp[i-1], dp[i-2]) that were already solved.

How can we apply this idea to a graph? In a general graph with cycles, it's not obvious which "subproblem" (vertex) to solve first. However, a DAG's defining feature—the absence of cycles—provides a clear dependency structure. A topological sort gives us a linear ordering of vertices such that for every directed edge from u to v, vertex u comes before vertex v. This ordering is precisely the "recipe" we need to solve our subproblems.

The general approach for DP on a DAG is:

1. Define a DP state, dp[v], which represents the solution to a subproblem ending at vertex v.
2. Process the vertices of the DAG in a topological order.
3. When processing a vertex v, compute dp[v] using the already computed DP values of its predecessors (vertices with an edge pointing to v).

The following reading explains this fundamental connection between topological sorting and dynamic programming on DAGs.

This principle transforms many graph problems into a straightforward, iterative process. Let's see it in action with a classic example.

2. Application: Shortest and Longest Paths in a DAG

One of the most common applications of DP on DAGs is finding the shortest or longest path from a single source vertex. While Dijkstra's and Bellman-Ford algorithms solve the single-source shortest path (SSSP) problem for general graphs, using DP on a DAG provides a simpler and often more efficient solution.

The key insight is that the shortest path to a vertex v must come from one of its immediate predecessors. If we process the vertices in topological order, we guarantee that by the time we evaluate v, we have already found the shortest paths to all its predecessors.

This leads to the following recurrence relation for the shortest path from a source s to any vertex v:

We initialize dist[s] = 0 and all other dist values to $\infty$. Then, we iterate through the topologically sorted vertices and apply this relaxation step.

The video below provides a fantastic visual walkthrough of this exact process.

This algorithm runs in $O(V+E)$ time: $O(V+E)$ for the topological sort (using Kahn's algorithm or DFS) and $O(V+E)$ for iterating through all vertices and their outgoing edges once. This is more efficient than Dijkstra's algorithm, which is typically $O(E\log V)$, and it also correctly handles negative edge weights, a case where Dijkstra's fails.

What about the Longest Path?

Finding the longest path in a general graph is an NP-hard problem. However, on a DAG, it's just as easy as finding the shortest path! We can solve it in linear time. There are two common ways:

1. Negate and Solve: A clever trick is to negate all edge weights in the graph and then run the SSSP algorithm. The "shortest" path in this modified graph corresponds to the longest path in the original graph.
2. Direct DP Formulation: Alternatively, we can modify the recurrence to use max instead of min and initialize distances to $-\infty$.

The following resource provides a clear explanation and pseudocode for this direct DP approach to the longest path problem.

3. Implementation: Topological Sort vs. Memoization

Given your software engineering background, it's valuable to consider the two main ways to implement a DP solution on a DAG. What we have described so far is a bottom-up approach, often called tabulation.

1. Tabulation (via Topological Sort):
   • First, explicitly compute a topological sort of all vertices.
   • Create a DP table (e.g., a dist array).
   • Iterate through the sorted vertices and compute the DP value for each one.
   • This approach solves the subproblem for every vertex in the graph.

An alternative is a top-down approach using memoization.

2. Memoization (via Recursion):
   • Write a recursive function solve(v) that computes the DP value for vertex v.
   • Inside solve(v), recursively call solve(u) for all predecessors u of v.
   • Store the result for solve(v) in a memoization table to avoid re-computation.
   • This approach only computes the DP values for vertices that are ancestors of the target vertex.

The following reading provides a concise comparison of these two styles.

In summary:

• Use tabulation with topological sort when you need to compute the solution for most or all nodes, or when you want to avoid recursion overhead. This is generally the standard and often more efficient approach for dense problems.
• Use memoization when you only need the solution for a specific target node (and its ancestors), and many other nodes in the graph are irrelevant.

Conclusion

In this lesson, we bridged the gap between graph theory and dynamic programming. By leveraging the unique acyclic property of DAGs, we can use topological sorting to create a linear, efficient DP algorithm.

Key Takeaways:

• A topological sort provides a natural computation order for dynamic programming on a DAG.
• The general DP strategy is to iterate through vertices in topological order, computing the DP state dp[v] based on the already-solved states of its predecessors.
• This pattern yields a linear time $O(V+E)$ algorithm for problems like single-source shortest and longest paths in a DAG, which is highly efficient and can handle negative weights.
• The implementation can be done iteratively (tabulation) with an explicit topological sort or recursively (memoization), with different performance trade-offs.

Preview of the Next Lesson:
We will continue this line of reasoning by narrowing our focus to an important subclass of DAGs: trees. Since every tree is also a DAG, the principles we learned today apply directly. In the next lesson, we will explore how to formulate and solve DP problems on trees, such as finding the maximum path sum between any two nodes.