DP on Graphs & DAGs
You are making change for 6 cents with coins of 1, 3 and 4. A greedy cashier hands over 4 + 1 + 1 — three coins. The best is 3 + 3 — two coins. Here is another way to see that problem: draw a dot for every amount 0, 1, …, 6, and an arrow from amount to for every coin . "Fewest coins" is now "fewest arrows from 0 to 6" — a shortest path. "How many ordered ways to pay" is "how many paths". The arrows only go forward (amounts only grow), so the picture has no cycles. It is a DAG: a directed acyclic graph.
This is not a trick that works for coin change only. Every dynamic program is a path problem on a DAG whose nodes are the DP states and whose edges are the transitions. Grid DP is a DAG of cells. Tree DP is a DAG of subtrees. Knapsack is a DAG of (item, capacity) pairs. Once you see the DAG, three things become obvious: the fill order (any topological order), the meaning of "optimal substructure" (a best path's prefix is a best path), and what goes wrong when the state graph has a cycle (no fill order exists; you need shortest-path algorithms instead).
This lesson makes that view concrete, then works through the problems where the DAG is the input itself: longest and shortest paths, path counting, counting shortest paths during Dijkstra, collapsing cycles with strongly connected components, longest increasing paths in matrices, scheduling with prerequisites, flights with a stop limit, and graphs where each node has exactly one outgoing edge.
You should know Topological Sort, Shortest Paths (Dijkstra and Bellman-Ford), and the basics of Tree DP. Connectivity is needed for the SCC section.
Why this exists
Longest path is NP-hard on general graphs: it contains the Hamiltonian path problem (a path of length through every vertex exists iff the longest simple path has edges). On a DAG it takes . The difference is the topological order: in a DAG you can line the vertices up so that every edge points right, and then "best path ending at " depends only on vertices to the left of , which are already finished. That is exactly the precondition for DP.
Richard Bellman, who coined "dynamic programming" in the 1950s, framed it as multistage decision processes, and the shortest-path view was there from the start: Bellman's 1958 paper "On a routing problem" is the Bellman-Ford algorithm, written as a DP over "number of edges used". The DAG view of DP is the organising idea of Dasgupta, Papadimitriou and Vazirani's Algorithms (Chapter 6 opens with "shortest paths in dags, revisited" and argues every DP has an underlying DAG). Thinking this way pays off in three practical ways:
- You can always find a fill order. Topologically sort the states, or let memoised recursion discover it.
- You can recognise when DP will fail. If states can reach themselves, there is no fill order.
- You can reuse graph algorithms. When the state graph has cycles but non-negative weights, Dijkstra on the state graph is the DP.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "tasks with prerequisites", "dependencies", "build order" and a max/min/count | DP in topological order |
| "longest path", "critical path", "maximum total along a route" in a DAG | Longest path DP, |
| "number of routes / ways from to ", "mod " in a DAG | Path counting: ways[v] = Σ ways[u] |
| "number of shortest paths", "how many fastest routes" | Dijkstra + a count array (shortest-path DAG) |
| "minimum number of flights / edges on a shortest route" alongside the count | Dijkstra with extra tie-breaking state |
| Directed graph with cycles, "you may revisit", "collect everything reachable" | SCC condensation, then DAG DP |
| "longest increasing path", moves in 4 directions but values must strictly increase | Memoised DFS: the strict increase makes it a DAG |
| "minimum number of semesters / rounds", "parallel courses" | Longest path counted in vertices (level-by-level Kahn) |
| "at most stops / edges / transfers" | Bellman-Ford rounds: dp[i][v] with edges |
| "each node points to exactly one next node", "teleporter", "successor" | Functional graph: trees hanging into cycles; binary lifting |
| "graph has a cycle → answer is infinite / " | Detect the cycle (Kahn leaves vertices) before DP |
| State transitions can go back ("snakes", "undo", "move left") | Not a DAG: BFS / Dijkstra / Bellman-Ford on states, or value iteration |
| "expected number of steps" with returns to earlier states | Linear equations or value iteration (see Probability DP) |
The meta-trigger: draw the states as dots and the transitions as arrows. If the arrows never form a loop, any DP works in topological order. If they do, either collapse the loops (SCCs), or switch to shortest-path algorithms.
Intuition & first principles
Every DP is a DAG of states
Take the coin example. States are amounts 0–6. From amount there is an edge to for each coin .
graph LR
A0["0"] --> A1["1"]
A0 --> A3["3"]
A0 --> A4["4"]
A1 --> A2["2"]
A1 --> A4
A1 --> A5["5"]
A2 --> A3
A2 --> A5
A2 --> A6["6"]
A3 --> A4
A3 --> A6
A4 --> A5
A5 --> A6
(Edges from 3 to 7 and beyond are dropped; they overshoot.) The DP for "fewest coins" is
which is a shortest path from 0 in this DAG with every edge of length 1. The DP for "number of ordered ways" is , the number of paths from 0. Computed by the lesson's script:
| Amount | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| best (fewest coins) | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
| ways (ordered sequences) | 1 | 1 | 1 | 2 | 4 | 6 | 9 |
The dictionary between the two languages:
| DP word | Graph word |
|---|---|
| state | vertex |
| transition / choice | edge (with a weight = the cost or gain of that choice) |
| base case | source vertex (or vertices) |
| "best value of a state" | shortest or longest path from a source to that vertex |
| "number of ways" | number of paths |
| fill order | topological order |
| memoisation | DFS that caches each vertex's answer |
| optimal substructure | a prefix of an optimal path is optimal |
| reconstruction | following parent pointers back from the target |
| "the DP has a cycle" | the state graph is not a DAG |
Why acyclic is the whole story
Suppose the best route to comes in through edge . Then the part before is a route to , and it must be a best route to (otherwise swap in the better one — the "cut and paste" argument from CLRS §14.3). So , maximised over incoming edges. This is only useful if is already known when we compute . In a DAG we can order vertices so that every edge goes from earlier to later. In a graph with a cycle , needs and needs : there is no "earlier".
For shortest paths with non-negative weights, cycles are harmless (going around a cycle never helps), and Dijkstra finds an order on the fly: it processes vertices by increasing distance. For longest paths, a positive cycle makes the answer infinite for walks, and for simple paths the problem becomes NP-hard. That asymmetry explains a lot of problem statements.
Two ways to get the order
- Push (tabulation in topological order). Compute a topological order (Kahn's algorithm: repeatedly remove a vertex with no remaining incoming edges). Process vertices in that order; each vertex pushes its finished value along its outgoing edges.
- Pull (memoised DFS).
solve(v)asks every predecessor (or successor, depending on direction) for its value, recursively, and caches the result. The recursion discovers a topological order by itself — this is DFS finishing order, as proven in Topological Sort. It visits only states reachable from the start, which can be a big saving when most states are irrelevant. The cost is recursion depth.
Mechanics
1. Longest path in a DAG, with reconstruction
Use this DAG with six vertices S, A, B, C, D, T and weighted edges:
graph LR
S["S"] -->|"3"| A["A"]
S -->|"2"| B["B"]
B -->|"1"| A
A -->|"4"| C["C"]
B -->|"6"| C
B -->|"2"| D["D"]
C -->|"1"| D
C -->|"3"| T["T"]
D -->|"5"| T
Goal: the heaviest path from S to T. State: best[v] = weight of the heaviest path from S to ( if is unreachable). Transition: for each edge , best[v] = max(best[v], best[u] + w). Order: topological. Reconstruction: store parent[v] = the that gave the max.
Kahn's algorithm gives the order S, B, A, C, D, T (A has to wait for B because of the edge B → A). Trace, with "candidates" listing every incoming edge's offer:
| Step | Vertex | Incoming candidates | best | parent | ways (column for section 2) |
|---|---|---|---|---|---|
| 1 | S | source | 0 | — | 1 |
| 2 | B | S: 0 + 2 | 2 | S | 1 |
| 3 | A | S: 0 + 3, B: 2 + 1 = 3 | 3 | S (tie; first one kept) | 2 |
| 4 | C | A: 3 + 4 = 7, B: 2 + 6 = 8 | 8 | B | 3 |
| 5 | D | B: 2 + 2 = 4, C: 8 + 1 = 9 | 9 | C | 4 |
| 6 | T | C: 8 + 3 = 11, D: 9 + 5 = 14 | 14 | D | 7 |
Follow parents back from T: T ← D ← C ← B ← S. The heaviest path is S → B → C → D → T with weight 2 + 6 + 1 + 5 = 14. Enumerating all 7 S→T paths by brute force confirms it (the others weigh 13, 10, 13, 10, 11 and 9).
Notice step 4. C's best comes from B directly (8), not through A (7). A greedy "always take the heaviest outgoing edge" walk from S would go S → A (3 beats 2), then A → C, and could never recover. The DP avoids this because it keeps the best value for every vertex, not just the current walk.
Shortest path in a DAG is the same sweep with min. Here it gives 9 (S → B → D → T). It works even with negative edge weights, because nothing depends on the "settle the closest vertex first" argument that Dijkstra needs. CLRS calls it DAG-SHORTEST-PATHS (§22.2 in the 4th edition, §24.2 in the 3rd), and Topological Sort works a second example plus critical-path scheduling.
Fixed source vs. any source
"Heaviest path from S" initialises only best[S] = 0 and everything else to , and must not relax edges out of vertices. "Heaviest path anywhere" initialises every vertex to 0 (a path may start anywhere) and takes the maximum over all vertices at the end. Mixing the two is the most common bug in this section.
2. Counting paths in a DAG (mod )
Replace "max of offers" with "sum of offers":
Every S→ path ends with exactly one incoming edge , and removing that edge leaves an S→ path, so this sum counts each path exactly once. The last column of the trace table shows the counts: 7 paths from S to T.
Counts explode. A chain of "diamonds" (each diamond offers two parallel routes) has paths: with that is about , far past 64 bits. Problems therefore ask for the count modulo a prime , usually . Since we only add, reduce after every addition. With 100 diamonds the answer is ; the implementations below test exactly that.
Counting paths needs a DAG, not just reachability
If the graph has a cycle reachable from S that can reach T, the number of walks from S to T is infinite. Check that Kahn's algorithm emitted every vertex (or at least every vertex on an S→T route) before trusting the count. Codeforces 919D "Substring" is built around exactly this "print −1 if there is a cycle" check.
3. Number of shortest paths, during Dijkstra
Now the graph may have cycles, but weights are positive. How many different shortest routes go from the source to each vertex?
Consider the subgraph of "tight" edges: with . Every shortest path uses only tight edges, and with positive weights the tight edges form a DAG (along a tight edge the distance strictly increases). The order in which Dijkstra pops vertices is increasing distance — a topological order of that DAG. So we can count paths in the shortest-path DAG while Dijkstra runs:
- When we find a strictly better distance to through :
dist[w] = dist[v] + c,cnt[w] = cnt[v](old routes are no longer shortest). - When we find an equally good one:
cnt[w] += cnt[v].
Example: undirected graph on vertices 0–4 with edges 0–1 (1), 0–2 (2), 1–2 (1), 1–3 (2), 2–3 (1), 3–4 (1), 2–4 (3); source 0.
graph LR
V0["0"] ---|"1"| V1["1"]
V0 ---|"2"| V2["2"]
V1 ---|"1"| V2
V1 ---|"2"| V3["3"]
V2 ---|"1"| V3
V3 ---|"1"| V4["4"]
V2 ---|"3"| V4
| Pop | Vertex | dist | cnt at pop | Why |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | source |
| 2 | 1 | 1 | 1 | only 0–1 |
| 3 | 2 | 2 | 2 | 0–2 directly (2) ties 0–1–2 (1 + 1) |
| 4 | 3 | 3 | 3 | via 1: 1 + 2 = 3 (1 way); via 2: 2 + 1 = 3 (2 ways) |
| 5 | 4 | 4 | 3 | via 3: 3 + 1 = 4 (3 ways); via 2: 2 + 3 = 5, not shortest |
There are 3 shortest routes from 0 to 4 (length 4): 0–1–3–4, 0–2–3–4 and 0–1–2–3–4. A brute-force enumeration of all simple paths agrees. This is CSES "Investigation" and LeetCode 1976 "Number of Ways to Arrive at Destination". The same pass can carry more DP values along the shortest-path DAG: the fewest and the most edges among shortest routes, or the best secondary score.
Zero-weight edges break the count
With a 0-weight edge and , Dijkstra may pop before . Then 's contribution reaches cnt[w] after has already pushed its count onward, and the downstream counts are too small. A cycle of 0-weight edges makes the count infinite. For example, with edges 0→2 (1), 0→3 (1), 3→2 (0) and 2→4 (1), a heap that breaks distance ties by vertex number pops 2 before 3 and reports 1 shortest route to 4 instead of 2 (checked by the lesson's script). With zeros, first compute distances, then build the tight-edge graph explicitly and count paths on it in a proper topological order (detecting 0-cycles).
4. DP over the SCC condensation
If a directed graph has cycles but you may revisit vertices, a common move is to collapse every strongly connected component (SCC: a maximal set of vertices that can all reach each other) into one super-vertex. The result, the condensation, is always a DAG (Connectivity proves it). Then do DAG DP on the condensation, provided the quantity behaves simply inside a component. "Collect coins in rooms you can revisit" behaves simply: inside an SCC you can walk to every room and come back, so you collect the whole component.
Small example: 6 rooms, coins [1, 2, 3, 4, 5, 6] in rooms 0–5, tunnels 0→1, 1→2, 2→0, 2→3, 3→4, 4→3, 4→5, 1→5.
graph LR
X["X = rooms 0,1,2: 6 coins"] --> Y["Y = rooms 3,4: 9 coins"]
X --> Z["Z = room 5: 6 coins"]
Y --> Z
DP on the condensation, sinks first: , , . The maximum collectable is 21: start in room 0, sweep rooms 0, 1, 2, go to 3, 4, then 5. CSES "Coin Collector" is this problem, solved in full on the Connectivity page. Tarjan's algorithm emits SCCs in reverse topological order of the condensation (sinks first), which is exactly the order this DP wants.
Problems that do not behave simply inside a component (say, "longest simple path") cannot be fixed this way: inside an SCC, simple-path questions remain NP-hard.
5. Longest increasing path in a matrix (memoised DFS)
Problem. In a grid of numbers, move up, down, left or right, always to a strictly larger number. What is the longest such path (counted in cells)? (LeetCode 329.)
Moves go in all four directions, which in Grid DP meant "not a DAG". Here the strict increase saves us: every move increases the value, so you can never return to a cell. The values themselves are a topological order. Two ways to use it:
- Memoised DFS ("pull"):
f(cell) = 1 + max f(neighbour)over larger neighbours, cached. - Sort cells by value, decreasing ("push"): process the largest values first; each cell reads its larger neighbours, already final. No recursion.
from functools import lru_cache
def longest_increasing_path_memo(m):
R, C = len(m), len(m[0])
@lru_cache(maxsize=None)
def f(r, c): # longest increasing path that starts at (r, c)
best = 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and m[nr][nc] > m[r][c]:
best = max(best, 1 + f(nr, nc))
return best
return max(f(r, c) for r in range(R) for c in range(C))
Matrix and the finished table f (computed by the test script):
matrix: 1 2 9 f: 7 6 1
5 3 8 1 5 2
4 6 7 5 4 3
The answer is 7: 1 → 2 → 3 → 6 → 7 → 8 → 9. Read the table back to recover it: from the 7 at (0,0), step to the neighbour holding 6 (cell (0,1)), then 5, 4, 3, 2, 1. The 5 at (1,0) has f = 1 because none of its neighbours (1, 3, 4) is larger.
Trace of the sorted ("push") version, largest values first:
| Value | Cell | Larger neighbours (their f) | f |
|---|---|---|---|
| 9 | (0,2) | none | 1 |
| 8 | (1,2) | 9 (1) | 2 |
| 7 | (2,2) | 8 (2) | 3 |
| 6 | (2,1) | 7 (3) | 4 |
| 5 | (1,0) | none | 1 |
| 4 | (2,0) | 5 (1), 6 (4) | 5 |
| 3 | (1,1) | 5 (1), 8 (2), 6 (4) | 5 |
| 2 | (0,1) | 9 (1), 3 (5) | 6 |
| 1 | (0,0) | 2 (6), 5 (1) | 7 |
Memoised DFS and stack depth
On a 200 × 200 matrix whose values snake through every cell, the recursion is 40,000 frames deep — beyond Python's default limit and Node's default stack. The implementations below use the sorted order. A third option is Kahn's algorithm on cells (indegree = number of smaller neighbours), which is instead of and yields the answer as the number of "layers" peeled.
Equal values are not connected (the move must be strictly larger), so the order among equal values does not matter. If a problem allowed "", equal neighbours would form cycles and the DP would break — exactly the "is it still a DAG?" question.
6. Course schedule with minimum semesters
Problem. Courses have prerequisites (a DAG). In each semester you may take any number of courses whose prerequisites are all done. What is the minimum number of semesters?
The answer is the number of vertices on the longest path — the depth of the deepest prerequisite chain. DP: sem[v] = 1 + max(sem[u]) over prerequisites (1 for courses with none). Level-by-level Kahn computes it directly: semester 1 = all sources; remove them; semester 2 = the new sources; and so on. If some course never becomes a source, there is a cycle and the schedule is impossible.
Example: prerequisites 1→3, 2→3, 3→4, 2→5, 5→6, 4→6. Semester 1: {1, 2}; 2: {3, 5}; 3: {4}; 4: {6}. 4 semesters, matching the chain 1 → 3 → 4 → 6.
Two variations show how quickly the problem changes:
- Courses have durations (LeetCode 2050, Parallel Courses III):
finish[v] = time[v] + max(finish[u]). That is the critical path method, worked through on Topological Sort. - At most courses per semester (LeetCode 1494, Parallel Courses II): the "take everything available" greedy fails, and the general problem — unit-time tasks with precedence on machines, minimising the finishing time — is NP-hard when is part of the input (Ullman, 1975). For a polynomial algorithm exists (Coffman and Graham, 1972); fixed is a long-standing open problem. With , LeetCode intends a Bitmask DP over the set of finished courses.
7. Cheapest flights within stops: Bellman-Ford as a layered DP
Problem. Flights with prices form a directed graph that may contain cycles. Find the cheapest route from src to dst with at most stops (at most flights). (LeetCode 787.)
Plain Dijkstra fails: the cheapest route might use too many flights, and Dijkstra keeps only one distance per city. The fix is to put the number of flights into the state. Let
Then , otherwise, and
The states form a layered DAG: every edge goes from layer to layer . The graph of cities can have cycles; the graph of (layer, city) states cannot. Computing layer from layer is exactly one round of Bellman-Ford — Bellman's original 1958 formulation.
Example: cities 0–4, flights 0→1 (100), 1→2 (100), 0→2 (500), 2→3 (100), 1→3 (600), 3→4 (100), 0→4 (1000), 2→4 (600); from 0 to 4.
| Layer (max flights) | city 0 | city 1 | city 2 | city 3 | city 4 | Best route to 4 |
|---|---|---|---|---|---|---|
| 0 | 0 | ∞ | ∞ | ∞ | ∞ | — |
| 1 | 0 | 100 | 500 | ∞ | 1000 | 0→4 |
| 2 | 0 | 100 | 200 | 600 | 1000 | 0→4 (0→2→4 costs 1100) |
| 3 | 0 | 100 | 200 | 300 | 700 | 0→2→3→4 |
| 4 | 0 | 100 | 200 | 300 | 400 | 0→1→2→3→4 |
So with or stops the answer is 1000; with it is 700; with it is 400. Each extra allowed flight can only help, which is why the table's columns never increase going down.
Relax from a copy of the previous layer
If you update dist in place during a round, an edge relaxed early in the round can feed another edge later in the same round, and a single round extends paths by several flights. On this example, in-place relaxation with edges in the listed order would let layer 1 already reach city 3 at cost 300 (0→1, 1→2, 2→3 all in one round) — wrong for "at most 1 flight". Always read from prev and write to cur.
Cost: time and space with two rolling layers. The Shortest Paths page shows the alternative of Dijkstra on the layered graph, , which is faster when most states are unreachable.
8. DP on functional graphs
A functional graph has exactly one outgoing edge per vertex: . Think "each planet has one teleporter". Every connected piece of it looks the same: one cycle, with trees hanging into it (the tree edges point toward the cycle).
graph LR
P7["7"] --> P0["0"]
P0 --> P1["1"]
P1 --> P2["2"]
P2 --> P3["3"]
P3 --> P1
P4["4"] --> P2
P5["5"] --> P6["6"]
P6 --> P5
The graph has cycles, so it is not a DAG — but its structure is so simple that DP still works in two phases:
- Find the cycles. Walk from each unvisited vertex, colouring vertices "on the current walk"; when you hit a vertex on the current walk, the part of the walk from there is a cycle. (Alternatively: Kahn's algorithm on indegrees peels off all tree vertices; what remains is exactly the cycle vertices.)
- Cycle vertices get their answer directly (often from the cycle length). Tree vertices satisfy a DAG recurrence pointing toward the cycle:
ans[v] = ans[f(v)] + 1. Process them in the reverse of the peeling order.
Example (CSES "Planets Cycles"): for each start, how many teleports until you land on a planet you have already visited? For (planet teleports to ), the cycle {1, 2, 3} has length 3 and {5, 6} has length 2. Cycle vertices answer their cycle length: 1, 2, 3 → 3; 5, 6 → 2. Tree vertices: 0 → 1 + ans[1] = 4; 4 → 1 + ans[2] = 4; 7 → 1 + ans[0] = 5. Answers: [4, 3, 3, 3, 4, 2, 2, 5], matching a step-by-step simulation.
"Where am I after teleports?" for huge uses binary lifting: up[j][v] = up[j-1][up[j-1][v]], the -th successor, a DP over (power, vertex) exactly like the ancestor table in LCA & Binary Lifting. preprocessing, per query (CSES "Planets Queries I"). LeetCode 2127 "Maximum Employees to Be Invited to a Meeting" is a harder functional-graph DP mixing cycle lengths with longest tree chains.
9. When the state graph has cycles
Sometimes the honest state graph has cycles and you cannot collapse them. Then "fill in topological order" has no meaning. What to do depends on the kind of value:
| Quantity | Cycles allowed? | Tool |
|---|---|---|
| Min cost, unit weights | yes | BFS on states (Snakes and Ladders, shortest path with obstacle removals) |
| Min cost, non-negative weights | yes | Dijkstra on states — it is the DP, with the order discovered by distance |
| Min cost, negative weights, no negative cycles | yes | Bellman-Ford on states; iterate until nothing changes ( rounds) |
| Max over walks with a positive cycle | — | Answer is unbounded; detect and report |
| Max over simple paths | yes | NP-hard in general; exponential search or bitmask DP for small |
| Count of walks / paths | — | Infinite if a cycle is on a route; otherwise DAG DP |
| Expected value / probability (random moves that can go back) | yes | Solve linear equations (Gaussian elimination) or value iteration until convergence — see Probability DP |
| Win/lose in a game with draws by repetition | yes | Retrograde analysis: BFS backwards from decided positions (Game DP) |
Snakes and Ladders (LeetCode 909) is the cleanest example. States are squares; from square you roll 1–6. Ladders jump forward, but snakes jump back, so square 40 might lead to square 12 and square 12 back to 40: a cycle. A naive DP moves[s] = 1 + min(moves[next]) loops forever or reads unfinished values. BFS from square 1 gives the fewest rolls correctly, because BFS processes states in order of distance — the right order when every edge costs 1.
Value iteration is the general fallback for "optimise expected cost" problems with cycles (Markov decision processes): start with any guess and apply the Bellman update repeatedly. With discounting (or a guaranteed eventual stop) it converges to the true values. It is Bellman-Ford's idea applied to expectations, and it is how reinforcement learning defines optimal value functions.
The ladder: brute force → better → optimal
Problem: heaviest path from S to T in a DAG with vertices and edges.
Rung 1: enumerate all paths
DFS from S, extend every path in every possible way, record the best weight on reaching T. Correct (in a DAG every walk is a simple path), but a DAG can have exponentially many paths: for diamonds. .
def heaviest_brute(adj, s, t):
best = None
stack = [(s, 0)]
while stack:
v, w = stack.pop()
if v == t:
best = w if best is None else max(best, w)
for u, c in adj[v]:
stack.append((u, w + c))
return best
Rung 2: memoised DFS
f(v) = heaviest path from to T ( if T unreachable). f(T) = 0, f(v) = max(c + f(u)) over edges . Each vertex is solved once, each edge looked at once: . Only vertices reachable from S are touched. The risk is recursion depth , and a cycle in the input would recurse forever unless you track "in progress" vertices (white/grey/black colouring, which doubles as cycle detection).
Rung 3: tabulation in topological order
Kahn's algorithm, then one sweep. , no recursion, and Kahn tells you for free whether the graph had a cycle (some vertices never reach indegree 0). This is the version in Implementation.
Side rung: negate weights and run a shortest-path algorithm
"Longest path = shortest path with negated weights." In a DAG this is fine (negative weights are no problem for the DAG sweep, and there are no cycles to be negative). Running Bellman-Ford instead would cost for no benefit, and Dijkstra is wrong with negative weights. On graphs with cycles, negating creates negative cycles — the NP-hardness has to show up somewhere.
| Rung | Method | Time | Extra space | Why it is better than the rung above |
|---|---|---|---|---|
| 1 | Enumerate paths | worst case | stack | Baseline, obviously correct |
| 2 | Memoised DFS | + recursion | Each vertex solved once; visits only reachable states | |
| 3 | Topological sweep | No recursion; detects cycles; easy reconstruction | ||
| side | Negate + Bellman-Ford | Works, but strictly slower on DAGs |
Correctness
Topological DP (longest/shortest path, counting). Induction over the topological order. Claim: when is processed, best[v] (and ways[v]) is correct. The source is correct by definition. Every path from S to ends with an edge , and in a topological order comes before , so was finished and pushed its offer before was processed. By optimal substructure, the best S→ path is the best S→ path plus the edge, for the right , and the max over all incoming offers includes it. For counting, the paths ending in different last edges are disjoint and cover everything, so the sum is exact.
Reconstruction. parent[v] is a with best[u] + w(u, v) = best[v]. Walking parents from T visits strictly earlier vertices (topological order), so it terminates at S, and the weights telescope to best[T].
Counting shortest paths with Dijkstra. With positive weights, every tight edge has , so is popped before (Dijkstra pops in non-decreasing distance; see the proof on Shortest Paths). When is popped its count is final (all its tight predecessors were popped earlier) and it adds that count to if the edge is tight. If a strictly better route to appears later, the reset cnt[w] = cnt[v] discards counts from edges that turned out not to be tight. When is popped, every tight in-edge has contributed exactly once.
Hop-limited Bellman-Ford. Induction on : is the cheapest walk with at most edges. A cheapest such walk either has at most edges (first term) or ends with an edge after a walk with at most edges to (second term). Reading only from layer is what makes the induction hypothesis apply.
SCC condensation. Proven on Connectivity: every walk visits components along a path of the condensation, and within a component any walk can collect everything.
Longest increasing path. The relation "move to a strictly larger neighbour" strictly increases the value, so it has no cycles; any order by decreasing value is a topological order of the reversed edges. The memoised DFS terminates for the same reason.
Functional graphs. Following from any vertex must eventually repeat a vertex (finitely many vertices), and from then on it loops forever on that cycle. Every vertex is either on a cycle or on a tree path into one, and the tree parts form a DAG pointing toward the cycles.
Complexity
| Problem | Time | Space | Notes |
|---|---|---|---|
| Longest / shortest path in a DAG | Plus for the graph; negative weights fine | ||
| Counting paths mod | One addition and one mod per edge | ||
| Number of shortest paths (Dijkstra) | Positive weights only | ||
| SCC condensation + DP | Tarjan or Kosaraju, then a DAG sweep | ||
| Longest increasing path (memo or Kahn) | Sorting version | ||
| Minimum semesters | Level-by-level Kahn | ||
| Cheapest flights, stops | Two rolling layers | ||
| Functional graph DP | Binary lifting: table | ||
| Value iteration | Converges geometrically with discount |
Integer sizes. Path weights in a DAG are at most : needs 64 bits. Path counts must be reduced mod after every addition; with , the sum of two residues fits in 32-bit signed integers, and even TypeScript's number stays exact.
Implementation
One program per language with three functions, all iterative (no recursion anywhere):
longestPath(n, edges, s, t)— Kahn's algorithm, heaviest S→T path, parent-pointer reconstruction; reports a cycle as an error and an unreachable T as "no path".countPaths(n, edges, s, t)— number of S→T paths modulo .longestIncreasingPath(matrix)— cells sorted by decreasing value, each reading its larger neighbours.
Each program asserts this lesson's examples: the S…T DAG (14 via S, B, C, D, T; 7 paths), 100 diamonds (), the 3×3 matrix (7) and two more matrices, and a cycle being rejected. The Python version was also checked against brute force on 500 random DAGs and 500 random matrices.
from typing import List, Optional, Tuple
MOD = 1_000_000_007
WEdge = Tuple[int, int, int] # (from, to, weight)
def topo_order(n: int, edges: List[Tuple[int, ...]]) -> List[int]:
"""Kahn's algorithm. Raises ValueError if the graph has a cycle."""
adj: List[List[int]] = [[] for _ in range(n)]
indeg = [0] * n
for e in edges:
adj[e[0]].append(e[1])
indeg[e[1]] += 1
order = [v for v in range(n) if indeg[v] == 0]
head = 0
while head < len(order): # the list doubles as the queue
v = order[head]
head += 1
for w in adj[v]:
indeg[w] -= 1
if indeg[w] == 0:
order.append(w)
if len(order) != n:
raise ValueError("graph has a cycle")
return order
def longest_path(n: int, edges: List[WEdge], s: int, t: int) -> Optional[Tuple[int, List[int]]]:
"""Heaviest s->t path in a DAG: (weight, vertices), or None if t is unreachable."""
out: List[List[Tuple[int, int]]] = [[] for _ in range(n)]
for a, b, w in edges:
out[a].append((b, w))
NEG = float("-inf")
best = [NEG] * n
parent = [-1] * n
best[s] = 0
for v in topo_order(n, edges):
if best[v] == NEG: # not reachable from s: offers nothing
continue
for w, c in out[v]:
if best[v] + c > best[w]:
best[w] = best[v] + c
parent[w] = v
if best[t] == NEG:
return None
path = [t]
while path[-1] != s:
path.append(parent[path[-1]])
path.reverse()
return int(best[t]), path
def count_paths(n: int, edges: List[Tuple[int, int]], s: int, t: int) -> int:
"""Number of s->t paths in a DAG, modulo 1e9+7."""
out: List[List[int]] = [[] for _ in range(n)]
for a, b in edges:
out[a].append(b)
ways = [0] * n
ways[s] = 1
for v in topo_order(n, edges):
if ways[v]:
for w in out[v]:
ways[w] = (ways[w] + ways[v]) % MOD
return ways[t]
def longest_increasing_path(m: List[List[int]]) -> int:
"""Longest strictly increasing 4-directional path, counted in cells."""
R, C = len(m), len(m[0])
cells = sorted(((m[r][c], r, c) for r in range(R) for c in range(C)), reverse=True)
f = [[1] * C for _ in range(R)] # f[r][c]: longest path starting at (r, c)
for value, r, c in cells: # larger values are already final
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and m[nr][nc] > value:
f[r][c] = max(f[r][c], 1 + f[nr][nc])
return max(max(row) for row in f)
if __name__ == "__main__":
S, A, B, Cc, D, T = range(6)
dag = [(S, A, 3), (S, B, 2), (B, A, 1), (A, Cc, 4), (B, Cc, 6),
(B, D, 2), (Cc, D, 1), (Cc, T, 3), (D, T, 5)]
assert longest_path(6, dag, S, T) == (14, [S, B, Cc, D, T])
assert longest_path(6, dag, A, B) is None # B is not reachable from A
assert count_paths(6, [(a, b) for a, b, _ in dag], S, T) == 7
k = 100 # 100 diamonds: 2^100 paths
diamonds = []
for i in range(k):
x = 3 * i
diamonds += [(x, x + 1), (x, x + 2), (x + 1, x + 3), (x + 2, x + 3)]
assert count_paths(3 * k + 1, diamonds, 0, 3 * k) == pow(2, k, MOD) == 976371285
try:
topo_order(3, [(0, 1), (1, 2), (2, 0)])
raise AssertionError("cycle not detected")
except ValueError:
pass
assert longest_increasing_path([[1, 2, 9], [5, 3, 8], [4, 6, 7]]) == 7
assert longest_increasing_path([[9, 9, 4], [6, 6, 8], [2, 1, 1]]) == 4
assert longest_increasing_path([[3, 4, 5], [3, 2, 6], [2, 2, 1]]) == 4
assert longest_increasing_path([[1]]) == 1
print("all DAG DP tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class DagDP {
static final long MOD = 1_000_000_007L;
static final long NEG = Long.MIN_VALUE;
/** Kahn's algorithm over edges given as {from, to, ...}. Throws if there is a cycle. */
static int[] topoOrder(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
int[] order = new int[n];
int tail = 0;
for (int v = 0; v < n; v++) if (indeg[v] == 0) order[tail++] = v;
for (int head = 0; head < tail; head++) { // the array doubles as the queue
for (int w : adj.get(order[head]))
if (--indeg[w] == 0) order[tail++] = w;
}
if (tail != n) throw new IllegalArgumentException("graph has a cycle");
return order;
}
/** Heaviest s->t path: returns the vertex list (weight in weightOut[0]), or null. */
static List<Integer> longestPath(int n, int[][] edges, int s, int t, long[] weightOut) {
List<List<int[]>> out = new ArrayList<>();
for (int i = 0; i < n; i++) out.add(new ArrayList<>());
for (int[] e : edges) out.get(e[0]).add(new int[]{e[1], e[2]});
long[] best = new long[n];
int[] parent = new int[n];
Arrays.fill(best, NEG);
Arrays.fill(parent, -1);
best[s] = 0;
for (int v : topoOrder(n, edges)) {
if (best[v] == NEG) continue; // unreachable from s
for (int[] wc : out.get(v))
if (best[v] + wc[1] > best[wc[0]]) { best[wc[0]] = best[v] + wc[1]; parent[wc[0]] = v; }
}
if (best[t] == NEG) return null;
List<Integer> path = new ArrayList<>();
for (int v = t; v != -1; v = (v == s ? -1 : parent[v])) path.add(v);
Collections.reverse(path);
weightOut[0] = best[t];
return path;
}
static long countPaths(int n, int[][] edges, int s, int t) {
List<List<Integer>> out = new ArrayList<>();
for (int i = 0; i < n; i++) out.add(new ArrayList<>());
for (int[] e : edges) out.get(e[0]).add(e[1]);
long[] ways = new long[n];
ways[s] = 1;
for (int v : topoOrder(n, edges))
if (ways[v] != 0)
for (int w : out.get(v)) ways[w] = (ways[w] + ways[v]) % MOD;
return ways[t];
}
static int longestIncreasingPath(int[][] m) {
int R = m.length, C = m[0].length;
Integer[] cells = new Integer[R * C];
for (int i = 0; i < R * C; i++) cells[i] = i;
Arrays.sort(cells, (x, y) -> Integer.compare(m[y / C][y % C], m[x / C][x % C])); // decreasing
int[][] f = new int[R][C];
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
int answer = 0;
for (int id : cells) {
int r = id / C, c = id % C;
f[r][c] = 1;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && m[nr][nc] > m[r][c])
f[r][c] = Math.max(f[r][c], 1 + f[nr][nc]);
}
answer = Math.max(answer, f[r][c]);
}
return answer;
}
public static void main(String[] args) {
int S = 0, A = 1, B = 2, C = 3, D = 4, T = 5;
int[][] dag = {{S, A, 3}, {S, B, 2}, {B, A, 1}, {A, C, 4}, {B, C, 6},
{B, D, 2}, {C, D, 1}, {C, T, 3}, {D, T, 5}};
long[] w = new long[1];
check(longestPath(6, dag, S, T, w).equals(List.of(S, B, C, D, T)) && w[0] == 14);
check(longestPath(6, dag, A, B, w) == null);
check(countPaths(6, dag, S, T) == 7);
int k = 100;
int[][] diamonds = new int[4 * k][];
for (int i = 0; i < k; i++) {
int x = 3 * i;
diamonds[4 * i] = new int[]{x, x + 1};
diamonds[4 * i + 1] = new int[]{x, x + 2};
diamonds[4 * i + 2] = new int[]{x + 1, x + 3};
diamonds[4 * i + 3] = new int[]{x + 2, x + 3};
}
check(countPaths(3 * k + 1, diamonds, 0, 3 * k) == 976371285L);
boolean threw = false;
try { topoOrder(3, new int[][]{{0, 1}, {1, 2}, {2, 0}}); }
catch (IllegalArgumentException e) { threw = true; }
check(threw);
check(longestIncreasingPath(new int[][]{{1, 2, 9}, {5, 3, 8}, {4, 6, 7}}) == 7);
check(longestIncreasingPath(new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}) == 4);
check(longestIncreasingPath(new int[][]{{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}) == 4);
check(longestIncreasingPath(new int[][]{{1}}) == 1);
System.out.println("all DAG DP tests passed");
}
static void check(boolean ok) {
if (!ok) throw new AssertionError("test failed");
}
}
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <iostream>
#include <optional>
#include <stdexcept>
#include <utility>
#include <vector>
using namespace std;
const long long MOD = 1'000'000'007LL;
// Kahn's algorithm; edges are {from, to, ...}. Throws if the graph has a cycle.
template <class E>
vector<int> topoOrder(int n, const vector<E>& edges) {
vector<vector<int>> adj(n);
vector<int> indeg(n, 0), order;
for (const auto& e : edges) { adj[e[0]].push_back(e[1]); ++indeg[e[1]]; }
for (int v = 0; v < n; ++v) if (indeg[v] == 0) order.push_back(v);
for (size_t head = 0; head < order.size(); ++head) // the vector doubles as the queue
for (int w : adj[order[head]])
if (--indeg[w] == 0) order.push_back(w);
if ((int)order.size() != n) throw invalid_argument("graph has a cycle");
return order;
}
// Heaviest s->t path: (weight, vertices), or nullopt if t is unreachable.
optional<pair<long long, vector<int>>> longestPath(int n, const vector<array<int, 3>>& edges,
int s, int t) {
vector<vector<pair<int, int>>> out(n);
for (auto& e : edges) out[e[0]].push_back({e[1], e[2]});
const long long NEG = LLONG_MIN;
vector<long long> best(n, NEG);
vector<int> parent(n, -1);
best[s] = 0;
for (int v : topoOrder(n, edges)) {
if (best[v] == NEG) continue; // unreachable from s
for (auto [w, c] : out[v])
if (best[v] + c > best[w]) { best[w] = best[v] + c; parent[w] = v; }
}
if (best[t] == NEG) return nullopt;
vector<int> path = {t};
while (path.back() != s) path.push_back(parent[path.back()]);
reverse(path.begin(), path.end());
return make_pair(best[t], path);
}
long long countPaths(int n, const vector<array<int, 2>>& edges, int s, int t) {
vector<vector<int>> out(n);
for (auto& e : edges) out[e[0]].push_back(e[1]);
vector<long long> ways(n, 0);
ways[s] = 1;
for (int v : topoOrder(n, edges))
if (ways[v])
for (int w : out[v]) ways[w] = (ways[w] + ways[v]) % MOD;
return ways[t];
}
int longestIncreasingPath(const vector<vector<int>>& m) {
int R = m.size(), C = m[0].size();
vector<int> cells(R * C);
for (int i = 0; i < R * C; ++i) cells[i] = i;
sort(cells.begin(), cells.end(),
[&](int x, int y) { return m[x / C][x % C] > m[y / C][y % C]; }); // decreasing
vector<vector<int>> f(R, vector<int>(C, 1));
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
int answer = 0;
for (int id : cells) {
int r = id / C, c = id % C;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C && m[nr][nc] > m[r][c])
f[r][c] = max(f[r][c], 1 + f[nr][nc]);
}
answer = max(answer, f[r][c]);
}
return answer;
}
int main() {
enum { S, A, B, C, D, T };
vector<array<int, 3>> dag = {{S, A, 3}, {S, B, 2}, {B, A, 1}, {A, C, 4}, {B, C, 6},
{B, D, 2}, {C, D, 1}, {C, T, 3}, {D, T, 5}};
auto res = longestPath(6, dag, S, T);
assert(res && res->first == 14 && (res->second == vector<int>{S, B, C, D, T}));
assert(!longestPath(6, dag, A, B));
vector<array<int, 2>> plain;
for (auto& e : dag) plain.push_back({e[0], e[1]});
assert(countPaths(6, plain, S, T) == 7);
int k = 100;
vector<array<int, 2>> diamonds;
for (int i = 0; i < k; ++i) {
int x = 3 * i;
diamonds.push_back({x, x + 1});
diamonds.push_back({x, x + 2});
diamonds.push_back({x + 1, x + 3});
diamonds.push_back({x + 2, x + 3});
}
assert(countPaths(3 * k + 1, diamonds, 0, 3 * k) == 976371285LL);
bool threw = false;
try { topoOrder(3, vector<array<int, 2>>{{0, 1}, {1, 2}, {2, 0}}); }
catch (const invalid_argument&) { threw = true; }
assert(threw);
assert(longestIncreasingPath({{1, 2, 9}, {5, 3, 8}, {4, 6, 7}}) == 7);
assert(longestIncreasingPath({{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}) == 4);
assert(longestIncreasingPath({{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}) == 4);
assert(longestIncreasingPath({{1}}) == 1);
cout << "all DAG DP tests passed\n";
return 0;
}
const MOD = 1_000_000_007;
// Kahn's algorithm over edges given as [from, to, ...]. Throws if the graph has a cycle.
function topoOrder(n: number, edges: number[][]): number[] {
const adj: number[][] = Array.from({ length: n }, () => []);
const indeg: number[] = new Array(n).fill(0);
for (const e of edges) {
adj[e[0]].push(e[1]);
indeg[e[1]]++;
}
const order: number[] = [];
for (let v = 0; v < n; v++) if (indeg[v] === 0) order.push(v);
for (let head = 0; head < order.length; head++) // the array doubles as the queue
for (const w of adj[order[head]]) if (--indeg[w] === 0) order.push(w);
if (order.length !== n) throw new Error("graph has a cycle");
return order;
}
// Heaviest s->t path: [weight, vertices], or null if t is unreachable.
function longestPath(n: number, edges: number[][], s: number, t: number): [number, number[]] | null {
const out: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
for (const [a, b, w] of edges) out[a].push([b, w]);
const best: number[] = new Array(n).fill(-Infinity);
const parent: number[] = new Array(n).fill(-1);
best[s] = 0;
for (const v of topoOrder(n, edges)) {
if (best[v] === -Infinity) continue; // unreachable from s
for (const [w, c] of out[v])
if (best[v] + c > best[w]) {
best[w] = best[v] + c;
parent[w] = v;
}
}
if (best[t] === -Infinity) return null;
const path = [t];
while (path[path.length - 1] !== s) path.push(parent[path[path.length - 1]]);
path.reverse();
return [best[t], path];
}
function countPaths(n: number, edges: number[][], s: number, t: number): number {
const out: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) out[a].push(b);
const ways: number[] = new Array(n).fill(0);
ways[s] = 1;
for (const v of topoOrder(n, edges))
if (ways[v] !== 0) for (const w of out[v]) ways[w] = (ways[w] + ways[v]) % MOD;
return ways[t];
}
function longestIncreasingPath(m: number[][]): number {
const R = m.length, C = m[0].length;
const cells: number[] = [];
for (let i = 0; i < R * C; i++) cells.push(i);
cells.sort((x, y) => m[Math.floor(y / C)][y % C] - m[Math.floor(x / C)][x % C]); // decreasing
const f: number[][] = Array.from({ length: R }, () => new Array<number>(C).fill(1));
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let answer = 0;
for (const id of cells) {
const r = Math.floor(id / C), c = id % C;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < R && nc >= 0 && nc < C && m[nr][nc] > m[r][c])
f[r][c] = Math.max(f[r][c], 1 + f[nr][nc]);
}
answer = Math.max(answer, f[r][c]);
}
return answer;
}
function assert(ok: boolean, msg = "test failed"): void {
if (!ok) throw new Error(msg);
}
const [S, A, B, C, D, T] = [0, 1, 2, 3, 4, 5];
const dag = [[S, A, 3], [S, B, 2], [B, A, 1], [A, C, 4], [B, C, 6],
[B, D, 2], [C, D, 1], [C, T, 3], [D, T, 5]];
const res = longestPath(6, dag, S, T);
assert(res !== null && res[0] === 14 && JSON.stringify(res[1]) === JSON.stringify([S, B, C, D, T]));
assert(longestPath(6, dag, A, B) === null);
assert(countPaths(6, dag, S, T) === 7);
const k = 100;
const diamonds: number[][] = [];
for (let i = 0; i < k; i++) {
const x = 3 * i;
diamonds.push([x, x + 1], [x, x + 2], [x + 1, x + 3], [x + 2, x + 3]);
}
assert(countPaths(3 * k + 1, diamonds, 0, 3 * k) === 976371285);
let threw = false;
try {
topoOrder(3, [[0, 1], [1, 2], [2, 0]]);
} catch {
threw = true;
}
assert(threw);
assert(longestIncreasingPath([[1, 2, 9], [5, 3, 8], [4, 6, 7]]) === 7);
assert(longestIncreasingPath([[9, 9, 4], [6, 6, 8], [2, 1, 1]]) === 4);
assert(longestIncreasingPath([[3, 4, 5], [3, 2, 6], [2, 2, 1]]) === 4);
assert(longestIncreasingPath([[1]]) === 1);
console.log("all DAG DP tests passed");
In countPaths, each ways[w] + ways[v] is below , which fits in a Java/C++ long long trivially and in a TypeScript number exactly. If you ever multiply two residues (path counts times a weight), JavaScript needs BigInt or a split multiplication, because .
Real-world uses
- Build systems. Make, Ninja and Bazel model targets and their dependencies as a DAG and rebuild in topological order. The critical path — the longest chain of dependent build steps by duration — bounds the wall-clock time of a fully parallel build; Bazel's build profile reports this critical path, and computing it is a longest-path DAG DP.
- Git's commit graph. Git's commit-graph file stores a generation number for each commit (version 1: one more than the maximum generation of its parents — a longest-path DP in the DAG of commits). Reachability queries such as
git merge-baseandgit log --graphuse it to stop walking early: a commit can only reach commits with a smaller generation. Introduced around Git 2.18–2.19 (Derrick Stolee's commit-graph work); see Git'sgitformat-commit-graphdocumentation. - Spreadsheets. A spreadsheet's formulas form a dependency DAG; recalculation evaluates cells in an order consistent with it, and a formula that refers back to itself is reported as a circular reference — the "cycle detected" branch of Kahn.
- Static timing analysis in chip design. Arrival times in a combinational circuit are computed by a longest-path sweep over the DAG of gates in topological order; the longest path is the critical path that limits the clock frequency.
- Speech, error correction and bioinformatics: the Viterbi algorithm. Decoding a hidden Markov model or a convolutional code finds the best path through a trellis, a layered DAG of (time, state) nodes (Viterbi, 1967). It is the cheapest-flights layering with probabilities instead of prices.
- Distance-vector routing. RIP routers run distributed Bellman-Ford; RIP caps routes at 15 hops and treats 16 as "unreachable" (RFC 2453), a hop-limited DP in the wild.
- Backpropagation. A neural network's computation graph is a DAG; reverse-mode automatic differentiation accumulates gradients in reverse topological order, summing contributions over all outgoing edges — structurally the path-counting DP with multiplication along edges.
- TeX line breaking. Knuth and Plass (1981) choose paragraph line breaks by a shortest path over the DAG of feasible breakpoints, minimising total "badness".
Pitfalls & edge cases
- Running DAG DP on a graph with a cycle. Kahn silently processes fewer than vertices; the DP then reads unfinished values. Always check the length of the order.
- Relaxing out of unreachable vertices ( in fixed-source longest path). In languages with integer sentinels this overflows or produces garbage. Skip vertices whose value is still the sentinel.
- "Any source" vs. "fixed source". Initialise all to 0 vs. only the source. Read the statement.
- Tie-breaking in reconstruction. Several parents may give the same best value; if the problem wants the lexicographically smallest path, the order you relax edges in matters. Decide deliberately.
- Counting shortest paths with zero-weight edges. Dijkstra's pop order is no longer a topological order of the tight-edge DAG. Build the tight graph explicitly.
- K stops vs. K edges. stops = flights. And relax from a copy of the previous layer.
- Memoised DFS depth. Longest increasing path on a 200×200 snake recurses 40,000 deep. Python's default limit is 1,000; Node overflows around a few thousand frames for typical DFS frames.
- Equal values in "increasing path" problems. Only strict increase gives a DAG.
- Modulo after every addition, and never compare counts after reducing them mod ("is this path count larger?" is meaningless mod ).
- Recursion on functional graphs. "Follow until you reach a known answer" by recursion can be deep. Peel with Kahn or walk with an explicit stack.
- SCC + DP with a quantity that is not "collect everything". Longest simple path inside an SCC is NP-hard; condensation does not help.
Variations
- Shortest path in a DAG with negative weights — same sweep with
min; faster than Bellman-Ford and correct where Dijkstra is not. - Critical path and slack — forward pass for earliest times, backward pass for latest times. See Topological Sort.
- Path with the most of one colour (LeetCode 1857, Codeforces 919D) — 26 counters per vertex,
cnt[v][c] = max over predecessors + [colour(v) = c], report −1 on a cycle. - Lexicographically smallest topological order / longest path — a priority queue instead of a FIFO in Kahn.
- Counting paths of exactly edges in a general graph — DP over (length, vertex), or Matrix Exponentiation of the adjacency matrix for huge .
- DP on the shortest-path DAG — after Dijkstra, any DAG DP over tight edges: number of shortest paths, the minimum/maximum number of edges among shortest paths (CSES "Investigation"), vertices that lie on every shortest path (count from both ends: , modulo hashing caveats).
- Layered state graphs — (vertex, coupons used), (vertex, fuel), (vertex, time mod ). Any bounded extra resource turns a cyclic graph into a DAG or a Dijkstra-friendly graph.
- Functional graphs with -step queries — binary lifting; "first time two walkers meet" — cycle detection with Floyd's tortoise and hare.
- Trees are DAGs — orient every edge away from the root and tree DP is DAG DP where each vertex has one parent. See Tree DP & Rerooting.
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. All Paths From Source to Target (LeetCode 797) — List every path from node 0 to node in a small DAG. Teaches the brute-force rung and why counting beats listing.
Hint
DFS with a path stack; at the target, copy the path. The output itself can be exponential, so no DP can make this polynomial.
2. Longest Path (AtCoder DP Contest G) — Length (in edges) of the longest directed path in a DAG with up to vertices. Teaches the "any source" longest path.
Solution
def longest_path_edges(n, edges):
out = [[] for _ in range(n)]
indeg = [0] * n
for a, b in edges:
out[a].append(b)
indeg[b] += 1
order = [v for v in range(n) if indeg[v] == 0]
for v in order: # appending while iterating = Kahn's queue
for w in out[v]:
indeg[w] -= 1
if indeg[w] == 0:
order.append(w)
best = [0] * n # any vertex may start a path
for v in order:
for w in out[v]:
best[w] = max(best[w], best[v] + 1)
return max(best)
assert longest_path_edges(4, [(0, 1), (0, 2), (2, 1), (1, 3), (2, 3)]) == 3
3. Longest Increasing Path in a Matrix (LeetCode 329) — The section 5 problem. Teaches "strict increase makes it a DAG".
Hint
The implementations above are full solutions. Try writing the Kahn-on-cells version and count layers.
4. Game Routes (CSES 1681) — Count paths from level 1 to level in a DAG, modulo . Teaches path counting.
Hint
count_paths from this lesson, with 1-based vertices.
5. Longest Flight Route (CSES 1680) — Visit as many cities as possible on a route from city 1 to city in a DAG, and print the route, or "IMPOSSIBLE". Teaches fixed-source longest path with reconstruction.
Solution
Weight every edge 1 and reuse longest_path; print IMPOSSIBLE when it returns None, otherwise the path (its length + 1 cities).
def longest_flight_route(n, flights): # cities 1..n
edges = [(a - 1, b - 1, 1) for a, b in flights]
res = longest_path(n, edges, 0, n - 1) # from this lesson's implementation
if res is None:
return None
_, path = res
return [v + 1 for v in path]
6. Cheapest Flights Within K Stops (LeetCode 787) — Section 7. Teaches layered Bellman-Ford.
Solution
def find_cheapest_price(n, flights, src, dst, k):
INF = float("inf")
prev = [INF] * n
prev[src] = 0
for _ in range(k + 1): # k stops = k + 1 flights
cur = prev[:] # read prev, write cur
for a, b, w in flights:
if prev[a] + w < cur[b]:
cur[b] = prev[a] + w
prev = cur
return -1 if prev[dst] == INF else prev[dst]
fl = [[0, 1, 100], [1, 2, 100], [0, 2, 500], [2, 3, 100],
[1, 3, 600], [3, 4, 100], [0, 4, 1000], [2, 4, 600]]
assert [find_cheapest_price(5, fl, 0, 4, k) for k in range(4)] == [1000, 1000, 700, 400]
7. Number of Ways to Arrive at Destination (LeetCode 1976) — Count shortest routes from 0 to in a weighted undirected graph, mod . Teaches Dijkstra + counts.
Solution
import heapq
MOD = 10**9 + 7
def count_shortest(n, roads):
adj = [[] for _ in range(n)]
for a, b, w in roads:
adj[a].append((b, w))
adj[b].append((a, w))
dist = [float("inf")] * n
cnt = [0] * n
dist[0], cnt[0] = 0, 1
pq = [(0, 0)]
while pq:
d, v = heapq.heappop(pq)
if d > dist[v]:
continue # stale queue entry
for w, c in adj[v]:
if d + c < dist[w]:
dist[w], cnt[w] = d + c, cnt[v]
heapq.heappush(pq, (dist[w], w))
elif d + c == dist[w]:
cnt[w] = (cnt[w] + cnt[v]) % MOD
return cnt[n - 1]
roads = [(0, 1, 1), (0, 2, 2), (1, 2, 1), (1, 3, 2), (2, 3, 1), (3, 4, 1), (2, 4, 3)]
assert count_shortest(5, roads) == 3
LeetCode's weights are at least 1, so the zero-weight trap does not apply.
8. Investigation (CSES 1202) — For the cheapest route from 1 to : its price, how many such routes, and the fewest and most flights among them. Teaches carrying several DP values along the shortest-path DAG.
Hint
Alongside cnt, keep mn[v] and mx[v] (edges). On a strictly better distance, copy and add 1; on a tie, mn = min(mn, mn[u] + 1), mx = max(mx, mx[u] + 1).
9. Parallel Courses III (LeetCode 2050) — Courses take given months; prerequisites must finish first; unlimited parallelism. Teaches longest path with vertex weights.
Hint
finish[v] = time[v] + max(finish[u]) in topological order; answer max(finish).
10. Course Schedule (LeetCode 207) — Can all courses be finished? Teaches the cycle check that every DAG DP needs.
Hint
Kahn; the answer is "processed count == n".
11. Largest Color Value in a Directed Graph (LeetCode 1857) — Max count of one colour along any path, or −1 if there is a cycle. Teaches multi-valued DAG states plus cycle detection.
Solution
def largest_path_value(colors, edges):
n = len(colors)
out = [[] for _ in range(n)]
indeg = [0] * n
for a, b in edges:
out[a].append(b)
indeg[b] += 1
cnt = [[0] * 26 for _ in range(n)] # cnt[v][c]: best count of colour c on a path ending at v
order = [v for v in range(n) if indeg[v] == 0]
best = 0
for v in order:
cnt[v][ord(colors[v]) - 97] += 1
best = max(best, max(cnt[v]))
for w in out[v]:
for c in range(26):
if cnt[v][c] > cnt[w][c]:
cnt[w][c] = cnt[v][c]
indeg[w] -= 1
if indeg[w] == 0:
order.append(w)
return best if len(order) == n else -1
assert largest_path_value("abaca", [[0, 1], [0, 2], [2, 3], [3, 4]]) == 3
assert largest_path_value("a", [[0, 0]]) == -1
12. Coin Collector (CSES 1686) — Section 4. Teaches SCC condensation + DAG DP.
Hint
Tarjan emits SCCs sinks-first; best[C] = coins[C] + max(best[C']) over condensation edges. Full code on Connectivity.
13. Planets Cycles (CSES 1751) — For each planet in a functional graph, steps until a repeat. Teaches cycle + tail DP.
Solution
def planets_cycles(succ):
n = len(succ)
ans = [0] * n
state = [0] * n # 0 new, 1 on current walk, 2 done
for s in range(n):
if state[s]:
continue
walk, v = [], s
while state[v] == 0:
state[v] = 1
walk.append(v)
v = succ[v]
if state[v] == 1: # found a new cycle starting at v
i = walk.index(v)
cycle = walk[i:]
for u in cycle:
ans[u] = len(cycle)
state[u] = 2
walk = walk[:i]
for u in reversed(walk): # tail vertices, nearest to the cycle first
ans[u] = ans[succ[u]] + 1
state[u] = 2
return ans
assert planets_cycles([1, 2, 3, 1, 2, 6, 5, 0]) == [4, 3, 3, 3, 4, 2, 2, 5]
14. Substring (Codeforces 919D) — Letters on vertices; the most frequent letter count along any path, or −1 if paths can be arbitrarily long. Teaches the same idea as LeetCode 1857 under contest limits.
Hint
Identical structure to problem 11; use fast input.
15. Maximum Employees to Be Invited to a Meeting (LeetCode 2127) — Each employee has one favourite; seat people at a round table next to their favourite. Teaches functional-graph DP: cycle lengths plus the longest tails into 2-cycles.
Hint
Answer = max(longest cycle length, sum over all 2-cycles of ), where tail is the longest chain hanging into that vertex, computed by Kahn peeling with depth[f[v]] = max(depth[f[v]], depth[v] + 1).
Common mistakes & interview follow-ups
"Why not just use Dijkstra with negated weights for longest path?" Dijkstra is incorrect with negative weights. In a DAG, the topological sweep is simpler, linear and correct. In a general graph, longest simple path is NP-hard.
"What if the graph might contain a cycle?" Run Kahn; if not all vertices come out, report the cycle (or condense SCCs if the problem allows revisiting).
"Can you do it recursively?" Yes — memoised DFS with three colours (unvisited, in progress, done); hitting an in-progress vertex means a cycle. Mention the recursion-depth risk for vertices.
"Count paths, but the count is huge." Modulo after every addition; mention exponential growth with the diamond example.
"Why does cheapest-flights need a copy of the array?" Show how in-place relaxation lets one round extend a path by several edges.
"How does this relate to DP in general?" States = vertices, transitions = edges, fill order = topological order. Memoisation = DFS. A DP with cyclic dependencies needs a different algorithm (BFS/Dijkstra/Bellman-Ford/value iteration).
Mistakes interviewers watch for: relaxing from unreachable vertices, forgetting the cycle check, confusing "stops" with "edges", in-place Bellman-Ford layers, recursion on large inputs, counts not reduced mod , and Dijkstra-based counting with zero weights.
Quick quiz
1. In the S…T DAG, why is A processed after B even though S → A comes first in the edge list?
Answer
Because of the edge B → A: A's indegree is 2 (from S and B), so it only reaches 0 after both S and B are processed. Kahn's order is S, B, A, C, D, T.
2. What is the fewest-coins answer for amount 6 with coins {1, 3, 4}, and how many ordered ways are there?
Answer
2 coins (3 + 3); 9 ordered sequences.
3. In the shortest-path counting example, why does vertex 4 have 3 shortest routes and not 3 + 2 = 5?
Answer
The route via 2 (2 + 3 = 5) is longer than the best distance 4, so its count is not added. Only tight edges contribute.
4. In the flights table, why can layer 1 not reach city 3?
Answer
Layer 1 allows one flight, and there is no direct flight 0 → 3. Updating in place would wrongly reach it in the same round via 0 → 1 → 2 → 3.
5. In , what is the answer for planet 7 and why?
Answer
5: planet 7 goes to 0 (1 step), and from 0 the answer is 4 (0, 1, 2, 3, then back to 1). 1 + 4 = 5.
6. A board game lets you move forward by dice rolls, but some squares send you backwards. Why can't you fill moves[square] from the last square to the first?
Answer
Backward jumps create cycles in the state graph, so a square's value can depend on a square that depends on it. Use BFS (fewest rolls) or linear equations / value iteration (expected rolls).
Further reading / sources
- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms (2006) — Chapter 6 opens with "Shortest paths in dags, revisited" and builds every DP on top of the DAG view.
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS) — single-source shortest paths in DAGs (§24.2 in the 3rd edition, §22.2 in the 4th), Bellman-Ford, Dijkstra, and the dynamic programming chapter's optimal-substructure argument.
- Richard Bellman, "On a routing problem", Quarterly of Applied Mathematics 16(1), 1958.
- Jeffrey D. Ullman, "NP-complete scheduling problems", Journal of Computer and System Sciences 10(3), 1975; E. G. Coffman and R. L. Graham, "Optimal scheduling for two-processor systems", Acta Informatica 1, 1972.
- Andrew J. Viterbi, "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm", IEEE Transactions on Information Theory 13(2), 1967.
- Donald E. Knuth and Michael F. Plass, "Breaking paragraphs into lines", Software: Practice and Experience 11(11), 1981.
- G. Malkin, RFC 2453, "RIP Version 2", 1998.
- Git documentation,
gitformat-commit-graph(generation numbers) and Derrick Stolee's commit-graph articles on the GitHub blog (2018–2019). - Antti Laaksonen, Competitive Programmer's Handbook — Chapter 16 "Directed graphs" (DAG DP, successor graphs, cycle detection).
- cp-algorithms, Topological sorting and Strongly connected components.
- CSES Problem Set, Graph Algorithms section — Game Routes, Longest Flight Route, Investigation, Coin Collector, Planets Cycles.
Lessons: previous — Tree DP & Rerooting · next — Bitmask DP · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Topological Sort · Shortest Paths · Connectivity · BFS · Graph Modeling · Grid DP · Probability DP · LCA & Binary Lifting.