Longest Path in DAG, in depth

Why acyclicity turns an NP-hard problem into a linear one

Shortest paths have a property that makes them tractable everywhere: any prefix of a shortest path is itself a shortest path. Longest simple paths in a general graph do not. The best way to reach v may pass through vertices that the best continuation from v also needs, and a path may not repeat a vertex. You cannot combine sub-answers, and nothing better than exponential search is known.

In a DAG the conflict disappears. No path can return to a vertex it has visited, so every path is automatically simple, and the best path into v cannot interfere with the best path out of it. That gives optimal substructure: the longest path ending at v is the longest path ending at some predecessor u, extended by the edge u -> v. The only remaining question is evaluation order, and a topological order answers it: when you reach v, every predecessor has a final answer. This is the general pattern from dynamic programming in depth applied to a graph.

The recurrence and a complete implementation

Let dist[v] be the length of the longest path ending at v. With edge weights w(u, v):

dist[v] = max( 0 if v may start a path else -inf,
               max over edges u -> v of dist[u] + w(u, v) )

The first term encodes the problem variant. For the longest path from a fixed source s, only s starts at 0 and everything else starts at negative infinity. Vertices unreachable from s stay at negative infinity, which is the right answer, not a bug. For the longest path anywhere in the graph, every vertex may start a path and starts at 0. The answer is then the maximum over all dist[v].

Many real problems put weights on vertices (task durations) rather than edges. Either fold the weight into the recurrence, dist[v] = w(v) + max(dist[u]), or split each vertex into an in-node and an out-node joined by an edge carrying its weight. The folded form is simpler and is what the code below uses for the scheduling example.

Here is a complete implementation with reconstruction. It uses Kahn's algorithm so that it can detect a cycle instead of returning a wrong answer:

from collections import deque

def longest_path(n, edges, source=None):
    """edges: list of (u, v, w). Returns (length, path). Raises on a cycle."""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v, w in edges:
        adj[u].append((v, w))
        indeg[v] += 1

    NEG = float("-inf")
    dist = [NEG] * n
    if source is None:
        dist = [0] * n               # any vertex may start a path
    else:
        dist[source] = 0
    parent = [-1] * n

    queue = deque(v for v in range(n) if indeg[v] == 0)
    seen = 0
    while queue:
        u = queue.popleft()
        seen += 1
        for v, w in adj[u]:
            if dist[u] != NEG and dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    if seen != n:
        raise ValueError("graph has a cycle; longest path is undefined")

    end = max(range(n), key=lambda v: dist[v])
    if dist[end] == NEG:
        return NEG, []
    path = []
    while end != -1:
        path.append(end)
        end = parent[end]
    return dist[path[0]], path[::-1]

Every vertex is dequeued once and every edge relaxed once, so it runs in O(V + E) time and O(V + E) space. The parent array costs one integer per vertex and turns a number into an explanation, which is usually what users actually want. The cycle check matters in production: real dependency graphs acquire cycles through configuration mistakes, and a longest-path routine that silently ignores the vertices stuck in a cycle reports a critical path that is too short.

Worked example: the critical path of a training pipeline

The best-known application is the critical path method. Take an ML training pipeline with seven tasks. Each task has a duration in minutes and can start only when its dependencies finish:

Forward pass. In topological order, earliest start is the maximum earliest finish over the task's dependencies, and earliest finish is earliest start plus duration. D waits for both B (finishing at 7) and C (finishing at 5), so it starts at 7. G finishes at 19. With unlimited workers, 19 minutes is the shortest possible makespan, and it equals the longest vertex-weighted path.

Backward pass. In reverse topological order, latest finish is the minimum latest start over the task's successors, with the final task's latest finish set to the makespan. Latest start is latest finish minus duration. E feeds only F, whose latest start is 16, so E may start as late as 15. Slack is latest start minus earliest start: how long a task can slip without delaying the whole pipeline.

def critical_path(tasks, deps, order):
    """tasks: {name: duration}; deps: {name: [prerequisites]}; order: topological."""
    es, ef = {}, {}
    for t in order:
        es[t] = max((ef[d] for d in deps.get(t, [])), default=0)
        ef[t] = es[t] + tasks[t]
    makespan = max(ef.values())
    succ = {t: [] for t in tasks}
    for t, ds in deps.items():
        for d in ds:
            succ[d].append(t)
    ls = {}
    for t in reversed(order):
        lf = min((ls[s] for s in succ[t]), default=makespan)
        ls[t] = lf - tasks[t]
    slack = {t: ls[t] - es[t] for t in tasks}
    return makespan, es, slack

The operational reading is direct. Speeding up E, the task with 12 minutes of slack, changes nothing. Cutting training (D) from 9 to 6 minutes cuts the pipeline to 16 minutes. Tokenizing (B) shows how the critical path moves: cutting it from 4 to 2 minutes saves 2 minutes (pipeline 17), and B and C then tie. Any further cut to B saves nothing, because C has become critical. Re-run the computation after every optimisation. With a fixed number of workers, optimal scheduling becomes NP-hard. Practical schedulers then use the longest remaining path from each task as a priority, which Kahn's algorithm as a live scheduler covers in detail.

Reductions and variants

Negate and run a shortest-path algorithm. On a DAG, the longest path under weights w is the shortest path under -w, and the DAG shortest-path DP handles negative weights fine. It is the same algorithm with min instead of max. Bellman-Ford also works on the negated DAG, because a DAG has no cycles and so no negative cycles, but it costs O(VE) for no benefit. Dijkstra does not work, because it assumes non-negative weights. On a graph with cycles, negation turns any positive cycle into a negative cycle. Shortest-path algorithms then report the negative cycle or fail, which is correct: the general problem did not become easy. Negation is a convenience for reusing a library, not a way around NP-hardness.

Count the optimal paths. Keep count[v] alongside dist[v]. When a relaxation strictly improves dist[v], set count[v] = count[u]. When it ties, add count[u]. This tells you whether a critical path is unique. If there are two, speeding up one does not shorten the pipeline.

Multiplicative weights. To find the most reliable path, where each edge has a success probability, maximise the sum of log(p). That is still a longest path, now with non-positive weights.

Longest increasing subsequence. Make one vertex per array index, with an edge from i to j whenever i < j and a[i] < a[j], and give each vertex weight 1. Index order is already a topological order, so the DP above gives an O(n^2) LIS. The specialised patience-sorting algorithm runs in O(n log n). The reduction is still useful because it shows immediately how to handle weighted variants, such as the heaviest increasing subsequence, which patience sorting does not cover directly.

Graphs that change. A build system or workflow engine edits its DAG continuously, and recomputing from scratch on every edge insert is wasteful on large graphs. Two pieces make it incremental. First, keep a valid topological order under insertions with an online algorithm, as described in batch versus online topological sort. Second, when an edge u -> v is added or a weight changes, recompute dist only for v and its descendants, in order, stopping along any branch where the value does not change. Deletions are harder, because a decrease can expose a different best predecessor. Many systems simply batch deletions and recompute periodically.

Failure modes

• Undetected cycles. A DFS-based order on cyclic input still emits an order, and the DP returns plausible numbers. Always check that every vertex was processed.
• Wrong initialisation. Starting every vertex at 0 when you meant a fixed source makes unreachable vertices look reachable, and the reported path starts somewhere unexpected.
• Recursion depth. A recursive DFS topological sort on a 100,000-vertex chain overflows Python's default recursion limit and can overflow a small thread stack in other languages. Use Kahn or an explicit stack.
• Non-deterministic ties. When two paths have equal length, the one reported depends on adjacency order. Break ties explicitly, for example by vertex ID, if reports are diffed between runs.
• Floating-point durations. Summing measured durations as floats makes "zero slack" come out as 1e-12. Compare slack with a tolerance or use integer milliseconds.
• Stale graphs. Critical paths computed from planned durations drift from reality. Recompute from measured durations on recent runs, not from estimates entered once.

What to do next

1. Implement longest_path in your language and test it on a chain, a diamond with tied paths, a graph with unreachable vertices and a graph with a cycle.
2. Export the dependency graph of one real pipeline or build, with measured durations, and compute its critical path and per-task slack.
3. Compare the makespan with the observed wall-clock time. A large gap means you are short of workers or losing time to queueing, not that the graph is slow.
4. Add path counting and report whether the critical path is unique before you invest in speeding up any single task.
5. Re-run the analysis after each optimisation and record how the critical path moves.
6. Practise recognising the pattern: solve LIS and one scheduling problem by explicitly building the DAG first.