You can topologically sort a DAG in O(V + E). You can do it with BFS or DFS. You can detect cycles for free. You know that multiple valid orderings exist and that the count reflects the graph's parallelism.

So what?

If topological sort were just about ordering tasks, the story would end here. But topological sort isn't the destination -- it's a tool. Specifically, it's a tool that turns a tangle of dependencies into a straight line. And once you have a straight line, you can do something remarkably powerful: walk along it from left to right, computing answers as you go.

Think of it like an assembly line. Before you can build a car, the chassis has to arrive before the engine mount, the engine before the wiring harness, the wiring before the dashboard. Topological sort figures out the assembly order. But the interesting question isn't “what order do I assemble in?” -- it's “what's the minimum time to build the whole car?” or “what's the most expensive path through the factory?” Those questions require dynamic programming along the assembly order.

Here's a weighted DAG. Each edge has a cost. The question: what's the longest path from the leftmost node to the rightmost? You could enumerate every possible path, sum the weights, and take the maximum. That works for small graphs. But the number of paths can grow exponentially with the graph size. There's a better way -- and it starts with the ordering you already know how to compute.

This 8-node weighted DAG has multiple paths from A to H. Each edge has a weight. Your challenge: find the longest path by tracing routes manually.

After a few paths, you'll feel the combinatorial pressure. Each branching node doubles the work. That frustration is the point. Then watch what happens when topological sort steps in.

Before the rescue, you'll predict: after topo sort arranges these nodes in a line, how many passes does the DP sweep need?

The brute-force approach checks every path. With 8 nodes and reasonable branching, that's maybe 6-10 paths -- manageable, but tedious. With 80 nodes? The path count could be astronomical. The exponential growth isn't obvious with small graphs, which is exactly why it's a trap in interviews. “Just enumerate the paths” sounds reasonable until the graph gets large.

The linearization rescue is almost unfair in its simplicity. One pass through the topological order, one Math.max comparison per edge. The topo sort handled the “in what order?” question. The sweep handled the “what's the best?” question. Together: O(V + E). No backtracking. No recursion. No memoization table. Just a for-loop.

This is the real power of topological sort. It's not about scheduling -- it's about enabling efficient computation on dependency graphs. The sort is the scaffolding; the DP is the building.

The graph is linearized. Below each node: a blank DP cell. Source A starts at 0. Fill the cells left to right.

For nodes with a single predecessor, the value is trivially computed -- these auto-fill to keep you focused on the interesting cases. For nodes with multiple predecessors, you must compare candidates and pick the maximum. That comparison is the entire cognitive challenge.

Every cell you filled followed the same pattern: look at incoming edges, compute dist[predecessor] + weight for each, take the max. The pattern is identical at every node -- only the numbers change. That's what makes it a for loop in code: the logic is the same, applied to each node in topo order.

The single-predecessor nodes were trivial because there's only one incoming path to consider. No comparison needed. The multi-predecessor nodes were interesting because you had to evaluate competing paths and select the winner. That evaluation is the Math.max call in the code. In a real implementation, you don't distinguish between the two cases -- the max of a single value is just that value. The code is uniform.

Notice that you never looked at a node before all its predecessors were filled. The topological order guaranteed that. Every time you computed dist[predecessor], the predecessor's value was already there. That's the magic of linearization: it turns a dependency graph into a sequential computation where every value you need is already computed by the time you need it.

Same graph. Same topological order. But now you can change the operator. What happens if you switch from max (longest path) to min (shortest path) or sum (count paths)?

Before each switch, predict which cells will change value. Cells with multiple predecessors are the interesting ones -- they're the nodes where the operator matters. A node with one predecessor gives the same result regardless of whether you take max, min, or sum of a single value.

Here's what's remarkable: the topological sort never changed. The graph structure never changed. The processing order never changed. The O(V + E) runtime never changed. The only thing that changed was one operator -- max to min to +. Three completely different problems, solved with the same scaffold.

That's the entire argument for why topological sort matters beyond scheduling. It's a compiler for dependency graphs. Once you linearize the DAG, any question that can be answered by processing nodes in dependency order becomes a single pass. Longest path, shortest path, path count, earliest finish time, latest start time, critical path -- they're all the same algorithm with different operators. The sort handles the ordering. The recurrence handles the question.

What you just did is one of the most powerful techniques in algorithm design. It has a simple structure:

Step 1: Topologically sort the DAG. This gives you a processing order where every node's dependencies come before it.

Step 2: Walk left to right along the ordering. At each node, compute a value from the values of its predecessors. The computation depends on what you're asking: max for longest path, min for shortest path, + for counting paths, or any other associative operation.

That's it. Step 1 is always the same. Step 2 changes based on the question. Together, they solve any “optimize over paths in a DAG” problem in O(V + E).

This is why topological sort matters beyond scheduling. It's a compiler for dependency graphs. Once you linearize the DAG, any question that can be answered by processing nodes in dependency order becomes a single pass. The topo sort handles the “in what order do I process?” question. The recurrence handles the “what do I compute?” question.

The classic example is course planning. Each course depends on prerequisites. Topological sort tells you a valid semester ordering. But DP on that ordering can answer richer questions: “What's the minimum number of semesters to graduate?” (longest chain through the prerequisite graph -- min semesters equals longest path + 1). “How many different valid course sequences exist?” (count paths). “What's the latest I can start a course and still graduate on time?” (reverse DP).

Every time you see a DAG -- build dependencies, task scheduling, spreadsheet cell computation, type inference, database migration ordering -- topological sort is the key that unlocks efficient computation. The sort itself is fast. The DP it enables is where the real power lives.

In competitive programming, “DP on DAGs” appears in disguise. Any time a problem says “count the number of ways to reach state X” or “find the shortest/longest sequence satisfying property Y” and the state transitions form a DAG (no cycles), the solution is: topo sort + one-pass DP. The sort is O(V + E). The sweep is O(V + E). The total is O(V + E). You can't do better.

Split screen: linearized DAG with DP cells on the left, the full longestPath implementation on the right. The topo sort phase fast-forwards -- you know that part. The DP sweep phase slows down for each Math.max comparison.

The code has two halves. The first half (lines 7-20) is Kahn's algorithm -- you've seen every line before. The second half (lines 22-28) is the DP sweep -- a single for loop over the topological order with one Math.max per edge. That's the entire implementation.

The beauty is that the two halves are independent. You could replace Kahn's with DFS post-order reversal and the DP sweep would work identically. You could replace Math.max with Math.min or + and the topo sort would work identically. The two concerns -- ordering and computation -- are cleanly separated.

In production code, you'd often compute the topological order once and reuse it for multiple DP queries. Sort the task graph once, then answer “critical path?” and “slack time?” and “number of valid schedules?” using the same ordering with different recurrences. The sort is the setup cost; each DP query is nearly free after that.

Three capstone tasks: DP from scratch, recurrence identification, and code modification. This is the culmination of seven modules.