DPAlgorithmaka DAG DP, topological DP, longest path in a DAG

DP on DAGs

State is a vertex; process vertices in topological order so every predecessor is finalized before its successors.

▶ Visualize Pattern: Topological Sort Practice (2)

Progress

Overview

Every DP is secretly a DAG of subproblems; DP on DAGs makes that explicit when the input is a graph. If a directed graph has no cycles, Topological Sort gives an order in which every edge goes forward, and any quantity defined as "best/count over paths ending at v" can be computed with one relaxation pass over the edges in that order: dp[v] = best over (u → v) of dp[u] + w(u, v). This solves longest path, shortest path with negative edges, number of paths, and reachability-with-constraints in O(V + E) — problems that are NP-hard or need heavier algorithms on general graphs.

Members: longest path in a DAG (critical path / project scheduling), number of paths from s to t, shortest path in a DAG with negative weights (no Bellman-Ford needed), Longest Increasing Path in a Matrix (edges to strictly larger neighbours), course-schedule-style "minimum semesters", and any problem whose state transitions form a graph given in the input.

Typical constraints: V, E ≤ 10^5–10^6. Both bottom-up (Kahn's BFS order, see Kahn's Algorithm) and top-down (memoized Depth-First Search (DFS), see DFS Topological Sort) work; Kahn's avoids recursion depth issues.

DAGtopological orderlongest pathpath countingO(V + E)

Intuition

A mental model before the formal terms.

A project plan: each task has a duration and prerequisites. The earliest finish time of a task is its duration plus the latest finish among its prerequisites. If you handle tasks in an order where prerequisites always come first, every task can be finalized in one look at its incoming arrows. The latest finish overall is the project length — the longest path.

Compare with a general graph: cycles would let "earliest finish" depend on itself. Acyclicity is exactly what makes a single pass sufficient.

How it works

State: dp[v] = optimal value over paths ending at v (or starting at v for the reverse formulation).
Transition: for each edge u → v: dp[v] = combine(dp[v], dp[u] + w(u, v)) — max for longest, min for shortest, + for counting.
Base cases: sources (in-degree 0): dp[s] = 0 (or 1 for counting paths from a specific source, 0 elsewhere).
Order: topological — Kahn's algorithm pushes in-degree-0 vertices to a queue, pops them, relaxes outgoing edges, and pushes successors whose in-degree hits 0. Alternatively, memoized DFS computes dp[v] on demand.
Answer: max over v of dp[v] for longest path; dp[t] for a target; also record parent[v] to reconstruct the path.

Why it works

In a topological order, all predecessors of v appear before v, so when v is processed every dp[u] it reads is final. Induction over the order proves each dp[v] correct.

Each vertex and edge is touched a constant number of times, hence O(V + E). Without cycles there is no need for repeated relaxation rounds (as in Bellman-Ford) or priority queues (as in Dijkstra).

Recognition

How to tell a problem wants this.

Directed graph explicitly stated to be acyclic, or a dependency/prerequisite structure, or edges defined by a strict order (smaller → larger value, earlier → later time).
Asks for longest path, number of paths, or an optimal path with negative weights on such a graph.
A memoized DFS "naturally" solves it with no visited-set trouble because there are no cycles.

“prerequisites” → Topological Sort “number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Kahn's Algorithm visualization.

Graph — One edge per line: "A B". Optional "source: A" / "target: F" lines.

Queue

shirtpantssocks

Topological order

empty

1/16Count incoming edges. Nodes with in-degree 0 have no prerequisites, so they can go first: shirt, pants, socks.

Current node (label = in-degree)In queue (in-degree 0)EmittedEdge being removedStuck in a cycle

PseudocodeLearn Kahn's Algorithm →

1indeg[v] = number of incoming edges
2queue = [v for v in nodes if indeg[v] == 0]
3while queue not empty:
4  u = queue.popleft(); order.append(u)
5  for v in neighbors(u):
6    indeg[v] -= 1
7    if indeg[v] == 0: queue.append(v)
8if len(order) < n: cycle detected

Complexity

best O(V + E)

avg O(V + E)

worst O(V + E)

space O(V)

Speed

Pseudocode

1# longest path in a DAG (edge weights w), Kahn's order
2indeg[v] = number of incoming edges
3dp[v] = 0 for all v; queue = all v with indeg 0
4while queue not empty:
5  u = pop()
6  for (v, w) in adj[u]:
7    dp[v] = max(dp[v], dp[u] + w)
8    indeg[v] -= 1
9    if indeg[v] == 0: push(v)
10return max(dp)   # if not all vertices popped, the graph has a cycle

Implementations

1import math
2from collections import deque
3 
4# DP on a DAG: acyclicity means a topological order exists, and processing
5# vertices in that order guarantees every predecessor is final before it is
6# read. That is the whole trick — no memo table, no recursion, one sweep.
7# Representative example: longest path, path counting, and shortest path with
8# negative weights (which Dijkstra cannot do but a DAG sweep can).
9 
10 
111 · Kahn's algorithm produces the order the sweep will follow
12def topo_order(adj: list[list[tuple[int, int]]]) -> list[int]:
13    n = len(adj)
14    indeg = [0] * n
15    for row in adj:
16        for v, _ in row:
17            indeg[v] += 1
18    ready = deque(u for u, d in enumerate(indeg) if d == 0)
19    order: list[int] = []
20    while ready:
21        u = ready.popleft()
22        order.append(u)
23        for v, _ in adj[u]:
24            indeg[v] -= 1
25            if indeg[v] == 0:
26                ready.append(v)
27    return order if len(order) == n else []
28 
29 
302 · Longest path: relax forward in topological order, taking the maximum
31def longest_path_from(adj: list[list[tuple[int, int]]], src: int) -> list[float]:
32    dist: list[float] = [-math.inf] * len(adj)
33    dist[src] = 0
34    for u in topo_order(adj):
35        if dist[u] == -math.inf:
36            continue  # unreachable from src
37        for v, w in adj[u]:
38            if dist[u] + w > dist[v]:
39                dist[v] = dist[u] + w
40    return dist
41 
42 
433 · Shortest path: identical sweep, min instead of max. Negative edges are
44# fine here, which is exactly what Dijkstra cannot handle.
45def shortest_path_from(adj: list[list[tuple[int, int]]], src: int) -> list[float]:
46    dist: list[float] = [math.inf] * len(adj)
47    dist[src] = 0
48    for u in topo_order(adj):
49        if dist[u] == math.inf:
50            continue
51        for v, w in adj[u]:
52            if dist[u] + w < dist[v]:
53                dist[v] = dist[u] + w
54    return dist
55 
56 
574 · Counting paths: the same sweep with addition instead of min or max
58def path_counts(adj: list[list[tuple[int, int]]], src: int) -> list[int]:
59    ways = [0] * len(adj)
60    ways[src] = 1
61    for u in topo_order(adj):
62        if ways[u] == 0:
63            continue
64        for v, _ in adj[u]:
65            ways[v] += ways[u]
66    return ways
67 
68 
695 · The longest path over the WHOLE dag: seed every vertex at 0
70def longest_path_anywhere(adj: list[list[tuple[int, int]]]) -> int:
71    dist = [0] * len(adj)
72    best = 0
73    for u in topo_order(adj):
74        for v, w in adj[u]:
75            if dist[u] + w > dist[v]:
76                dist[v] = dist[u] + w
77            best = max(best, dist[v])
78    return best

Walkthrough

for v, _ in row unpacks the pair and discards the weight with the conventional underscore.
collections.deque gives an O(1) ready queue with no head-cursor workaround.
The explicit if dist[u] + w > dist[v] comparison instead of max(...) avoids a Python-level function call in the innermost loop.
path_counts returns list[int] and is *exact* at any magnitude — Python integers are unbounded, so exponential path counts are never truncated.
-math.inf and math.inf are the sentinels, and both saturate under addition.

Complexity (this implementation)

time O(V + E) for the topological sort and for each sweep · space O(V)

Path counting is exact here at any size, unlike JS/TS (2^53) and C++ (long long overflow).

Language notes

graphlib.TopologicalSorter (3.9+) is the standard-library topological sort and raises CycleError rather than returning a sentinel.
Using math.inf makes the distance lists list[float] even for integer weights; a large integer sentinel keeps them list[int].
networkx.dag_longest_path and dag_longest_path_length implement the longest-path sweep directly.
Explicit comparisons beat max()/min() in a hot Python loop because they avoid a function call per candidate.

Common mistakes in this language

Using a list with pop(0) for the ready queue.
Leaving math.inf in a list that downstream code expects to hold integers.
Sweeping a cyclic graph without checking that the order covers every vertex.

Language differences that matter here

Path counting exposes the integer story: Python is exact at any magnitude, C++ overflows long long eventually, and JS/TS silently lose precision past 2^53 unless moved to BigInt.
The ready queue splits as always: collections.deque and std::queue are O(1) at the front, JS/TS need the head-cursor array.
Sentinels: Infinity/math.inf saturate safely, while C++ needs LLONG_MAX / 4 headroom so an accidental relaxation cannot overflow.
Only Python ships a topological sort in the standard library (graphlib), and it is also the only one whose built-in version signals a cycle by raising rather than by returning a short or empty order.

Complexity

Best

—

Average

—

Worst

O(V + E)

Space

O(V + E)

Topological sort and the relaxation pass are both linear. Memoized DFS has the same bound plus recursion depth up to V.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Longest/shortest path or path counting on a graph known to be acyclic.
Dependency scheduling: critical path, minimum number of rounds/semesters.
Implicit DAGs: strictly increasing moves on a grid, states ordered by a monotone key.

Avoid it when

The graph may contain cycles — topological order does not exist; use Dijkstra's Algorithm / Bellman-Ford for shortest paths (longest path is NP-hard on general graphs).
Unweighted shortest path from one source — plain Breadth-First Search (BFS) is simpler.
You need all-pairs answers on a dense graph — Floyd-Warshall may be more direct.

Alternatives

Topological Sort Kahn's Algorithm DFS Topological Sort Dijkstra's Algorithm Bellman-Ford Tree DP

Common mistakes

Skipping the cycle check — a cycle silently leaves vertices unprocessed and the answer wrong.
Initializing dp to 0 for all vertices when paths must start at a specific source — use -INF for non-sources (longest) or 0 ways (counting).
Relaxing edges in input order instead of topological order — predecessors may not be final.
Deep recursion in the memoized-DFS variant on long chains; prefer Kahn's for V ≥ 10^5.

Interview patterns

Longest Increasing Path in a Matrix (memoized DFS on the implicit DAG).
Parallel Courses / minimum semesters (longest path in prerequisite DAG).
All Paths From Source to Target (count/enumerate paths), Number of Ways to Arrive at Destination (Dijkstra + DAG counting).
Course Schedule with additional constraints; Alien Dictionary follow-ups.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
When space complexity mattersIntermediate
Choosing a shortest-path algorithmAdvanced
Recognizing a dynamic-programming problemAdvanced

Mock interviews

Course ScheduleIntermediate
Coin ChangeIntermediate

Example problems

Course Schedulemedium Alien Dictionaryhard

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related