Longest Path in a DAG

Longest Path in a DAG is one of the rare longest-path problems that is actually easy. In a general graph, longest path is NP-hard — but the moment the graph is a directed acyclic graph (DAG), a topological order turns it into a clean one-pass dynamic program.

The slow way first

You could enumerate every path from every starting vertex with DFS and keep the maximum. But the number of paths can be exponential, and you would recompute the same sub-paths over and over. Each vertex's best result depends only on its predecessors, so there is heavy overlap begging to be cached.

The idea: relax in topological order

Define dp[v] = the length of the longest path that ends at v. A path ending at v arrives along some incoming edge u→v of weight w, after a longest path ending at u. So:

dp[v] = max over every predecessor u of (dp[u] + w), or 0 if v has no incoming edges.

The catch: to use dp[u], it must already be final. A topological order guarantees exactly that — every vertex comes after all of its predecessors. Process vertices in that order and each dp[u] you read is done.

Walk through it

Step through the animation. After fixing the order A, B, C, D, E, each vertex lights up in turn. A has no predecessors, so dp[A] = 0. B only comes from A: dp[B] = 0 + 3 = 3. D has two incoming edges, so we take the better one: max(dp[B]+4, dp[C]+1) = max(7, 3) = 7. By the end, dp[E] = 9 is the largest value — the answer.

Pseudocode

order = topological_sort(vertices)
dp[v] = 0 for every vertex
preds[v] = list of (u, weight) edges pointing into v
for v in order:               # predecessors already finalized
    for (u, w) in preds[v]:
        dp[v] = max(dp[v], dp[u] + w)
return max(dp[v] over all v)

The Python solution

def longest_path(n, edges):
    order = topo_sort(n, edges)
    dp = [0] * n
    preds = build_predecessors(edges)
    for v in order:
        for u, w in preds[v]:
            cand = dp[u] + w
            dp[v] = max(dp[v], cand)
    return max(dp)

• order is a topological ordering of the vertices, so each vertex appears after all its predecessors.
• dp[v] starts at 0 — the longest path ending at a vertex with nothing flowing into it is empty.
• preds[v] lists each incoming edge as a (source, weight) pair.
• The inner loop is the relaxation: line 7 builds the candidate dp[u] + w and line 8 keeps the best.
• Because we go in topological order, every dp[u] we read on line 7 is already final.
• max(dp) is the longest path that ends anywhere, which is the global longest path.

Complexity

Every edge is examined exactly once during relaxation, so the whole algorithm is linear — the same cost as a single graph traversal.

When this pattern shows up

Practice