DP on DAGs: Longest Path
What You'll Learn
You'll learn how to find the longest path in a directed acyclic graph (DAG) by combining topological sorting with dynamic programming.
The Core Problem
In most graphs, finding the longest path is extremely difficult (NP-hard). But DAGs are special—their acyclic structure lets us use DP efficiently!
The key insight: process nodes in topological order. This guarantees that when you compute a node's longest path, all paths leading to it have already been computed.
How It Works
Think of a DAG like courses with prerequisites. You can't take Advanced Algorithms before Data Structures. The topological order ensures you always process prerequisites first.
The Algorithm
- Compute topological order of the DAG
- Initialize: Set distance to starting node as 0, all others as negative infinity
- Process in topological order: For each node
u:- For each outgoing edge
u → vwith weightw: - Update
dist[v] = max(dist[v], dist[u] + w)
- For each outgoing edge
- Result: Maximum value in
dist[]is the longest path length
Why Topological Order Matters
Since you process nodes in dependency order, when you reach node v, all possible paths ending at v have already been considered. This prevents cycles from breaking the computation and ensures each subproblem is solved exactly once.
Time Complexity
O(V + E) — you visit each vertex and edge once during topological sort and DP update.
Analogy
Imagine climbing a mountain with checkpoints. You can only reach higher checkpoints from lower ones. At each checkpoint, you record the longest trail taken so far. By the summit, you know the longest possible route.
Key Takeaway: Longest path in a DAG is efficiently solvable using DP over topological order, leveraging the acyclic structure to ensure subproblems are resolved before they're needed.