On this page

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:

  1. You can always find a fill order. Topologically sort the states, or let memoised recursion discover it.
  2. You can recognise when DP will fail. If states can reach themselves, there is no fill order.
  3. 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/countDP in topological order
"longest path", "critical path", "maximum total along a route" in a DAGLongest path DP,
"number of routes / ways from to ", "mod " in a DAGPath 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 countDijkstra 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 increaseMemoised 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 statesLinear 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 0123456
best (fewest coins)0121122
ways (ordered sequences)1112469

The dictionary between the two languages:

DP wordGraph word
statevertex
transition / choiceedge (with a weight = the cost or gain of that choice)
base casesource 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 ordertopological order
memoisationDFS that caches each vertex's answer
optimal substructurea prefix of an optimal path is optimal
reconstructionfollowing 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:

StepVertexIncoming candidatesbestparentways (column for section 2)
1Ssource0—1
2BS: 0 + 22S1
3AS: 0 + 3, B: 2 + 1 = 33S (tie; first one kept)2
4CA: 3 + 4 = 7, B: 2 + 6 = 88B3
5DB: 2 + 2 = 4, C: 8 + 1 = 99C4
6TC: 8 + 3 = 11, D: 9 + 5 = 1414D7

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
PopVertexdistcnt at popWhy
1001source
2111only 0–1
32220–2 directly (2) ties 0–1–2 (1 + 1)
4333via 1: 1 + 2 = 3 (1 way); via 2: 2 + 1 = 3 (2 ways)
5443via 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:

  1. Memoised DFS ("pull"): f(cell) = 1 + max f(neighbour) over larger neighbours, cached.
  2. 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:

ValueCellLarger neighbours (their f)f
9(0,2)none1
8(1,2)9 (1)2
7(2,2)8 (2)3
6(2,1)7 (3)4
5(1,0)none1
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 0city 1city 2city 3city 4Best route to 4
00∞∞∞∞—
10100500∞10000→4
2010020060010000→4 (0→2→4 costs 1100)
301002003007000→2→3→4
401002003004000→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:

  1. 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.)
  2. 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:

QuantityCycles allowed?Tool
Min cost, unit weightsyesBFS on states (Snakes and Ladders, shortest path with obstacle removals)
Min cost, non-negative weightsyesDijkstra on states — it is the DP, with the order discovered by distance
Min cost, negative weights, no negative cyclesyesBellman-Ford on states; iterate until nothing changes ( rounds)
Max over walks with a positive cycle—Answer is unbounded; detect and report
Max over simple pathsyesNP-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)yesSolve linear equations (Gaussian elimination) or value iteration until convergence — see Probability DP
Win/lose in a game with draws by repetitionyesRetrograde 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.

RungMethodTimeExtra spaceWhy it is better than the rung above
1Enumerate paths worst case stackBaseline, obviously correct
2Memoised DFS + recursionEach vertex solved once; visits only reachable states
3Topological sweepNo recursion; detects cycles; easy reconstruction
sideNegate + Bellman-FordWorks, 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

ProblemTimeSpaceNotes
Longest / shortest path in a DAGPlus 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 + DPTarjan or Kosaraju, then a DAG sweep
Longest increasing path (memo or Kahn)Sorting version
Minimum semestersLevel-by-level Kahn
Cheapest flights, stopsTwo rolling layers
Functional graph DPBinary lifting: table
Value iterationConverges 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-base and git log --graph use 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's gitformat-commit-graph documentation.
  • 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.