DP on DAGs

A directed acyclic graph (DAG) is a graph where edges point in one direction and there are no cycles — no way to follow edges and arrive back where you started. That sounds like a restriction, but it is actually a superpower.

Because there are no cycles, a DAG has a topological order: a way to list every node so that all edges point forward — from earlier entries in the list to later ones. Think of it like a schedule: task B can only start after task A finishes, and the topological order simply lists tasks in a valid execution sequence.

Once you have that order, dynamic programming becomes trivial. To compute the optimal value at any node, you only need to look at the nodes that come before it — and those have already been processed. A single left-to-right sweep over the topologically sorted nodes solves the entire problem.

This is not a niche trick. Shortest paths in a DAG, longest paths (critical path scheduling), the number of paths between two nodes, the probability of reaching a target — all collapse to the same linear scan. The key insight, proven by the structure of DAGs themselves, is that optimal substructure + topological order = one pass.

The graph below has seven nodes. Every edge has a weight (shown on the arrow). Click Topological DP to watch the algorithm assign the shortest distance from node S to every other node in one left-to-right sweep over the topological order.

<p class="hint">{{hint}}</p>
<canvas id="dag" width="560" height="320"></canvas>
<div class="status" id="status">{{press_run}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; background: #f4f7fa; border-radius: 10px; max-width: 100%; border: 1px solid #dce3ea; }
.status { font-size: .95rem; font-weight: 600; margin: .55rem 0 .4rem; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice that each node is visited exactly once. As soon as the algorithm reaches a node, all its predecessors have already been settled — so it can immediately compute the optimal distance by scanning incoming edges. No priority queue, no re-relaxation: just a single pass over the sorted nodes, each processed in O(incoming edges) time, giving $O(V + E)$ total.

How fast is DP on a DAG, and why can't general graphs do the same?

• Topological sort costs $O(V + E)$ — one DFS or a Kahn's algorithm BFS — and it is unique (up to ties among equally valid orderings) when the graph is a DAG.
• The DP sweep also costs $O(V + E)$: each node is processed once, and each edge is relaxed once. Total work is therefore $O(V + E)$, which is optimal — you cannot solve shortest paths without at least reading every edge.
• Compare with Dijkstra: on a general weighted graph with no negative edges, Dijkstra needs O((V + E) log V) for a binary heap. On a DAG it is unnecessary — topological order already guarantees no node is visited before all its predecessors.
• Negative edges? No problem. Bellman-Ford needs $O(VE)$ to handle negative weights safely. On a DAG, topological order handles any weight, positive or negative, in linear time — because cycles are what make negative weights dangerous, and a DAG has none.
• Longest path. On a general graph, longest path is NP-hard (it subsumes Hamiltonian path). On a DAG, negate all weights and run the same DP — still $O(V + E)$. This is why project scheduling (critical path method, CPM) uses DAGs.

The secret is that the structure of a DAG eliminates the hard part. There is no search, no backtracking, no exponential explosion. The topological order is a certificate that every sub-problem is already solved before you need it.

The "process nodes in topological order" pattern appears across computer science whenever there are dependencies:

• Critical path scheduling (CPM / PERT): model a project as a DAG of tasks with durations. The longest path gives the minimum project duration. Used in construction, manufacturing, and software releases.
• Build systems: Make, Bazel, and Ninja all represent source-file dependencies as DAGs and compile in topological order. A changed file triggers recompilation of all descendants — found by a reverse topological scan.
• Sequence alignment (edit distance): the classic DP table for sequence alignment is a grid whose cells form a DAG (each cell depends only on the cell to the left, above, and diagonally). Filling it row by row is topological DP in disguise.
• Probability and Bayesian networks: in a Bayesian network (a DAG of random variables), computing marginal probabilities by message-passing follows topological order. This is the backbone of spam filters, medical diagnosis tools, and language models.
• Compiler data flow: live-variable analysis, reaching definitions, and constant propagation all propagate information along a control-flow graph. When loops are absent or abstracted away, the graph is a DAG and the analysis is a single topological sweep.
• Coin change and knapsack on ordered items: many DP problems on sequences — coin change, knapsack — are secretly topological DP on an implicit DAG of states.

Whenever you see a table filled row by row, a pipeline processed stage by stage, or a scheduler that respects prerequisites, you are almost certainly looking at topological DP.

The lesson of DP on DAGs is not a clever trick — it is a principle: structure eliminates search. The moment you recognize that your problem's dependencies form a DAG, you know that a topological ordering exists, that optimal substructure holds trivially, and that a single $O(V + E)$ sweep will find the answer.

That is why topological DP quietly powers build tools, project schedulers, compilers, and probabilistic models. The hard problems — longest path on arbitrary graphs, optimal schedules with arbitrary dependencies — are NP-hard. But on a DAG, the same question becomes a clean linear scan.

The next time you fill in a DP table row by row, pause and ask: what is the DAG behind this table? The answer will almost always be there, and with it, the guarantee that no more than one pass is ever needed. See also how shortest paths generalize this idea to graphs with cycles, where topological order is no longer available.