vault

DAG Shortest and Longest Path

19 min read

DAG Shortest and Longest Path

When the input graph is a Directed Acyclic Graph (DAG) — directed edges, no directed cycles — both the single-source shortest path and the single-source longest path can be computed in O(V + E) time using a single linear scan over a topological ordering of the vertices. This is strictly better than Dijkstra’s O((V + E) log V), works with negative edge weights (because DAGs cannot contain negative cycles), and — most strikingly — solves the longest-path problem in linear time on DAGs even though longest path is NP-hard on general graphs. The technique is the foundation of the Critical Path Method (CPM) introduced by Kelley & Walker (1959) for project scheduling, where it answers questions like “what is the minimum time to finish this project?” and “which tasks must not slip if the deadline is to be met?” The same algorithm underlies build-system time estimation (Bazel, Make, Buck), gate-level circuit timing analysis, and interview-favourite DAG dynamic-programming problems.

1. Intuition — Filling in a Project Schedule from Earliest Possible Start Times

Imagine you’re managing a construction project. There are tasks (pour foundation, frame walls, install electrical, drywall, paint, inspect) with dependency rules (you can’t drywall until walls are framed and electrical is installed). Each task has a duration. Two natural questions:

  1. Earliest possible finish time. Walking through tasks in dependency order, the earliest you can start any task is max(earliest finish of all its prerequisites); the earliest finish is that plus its duration. By processing tasks in topological order — never visiting a task before all its prerequisites — every needed value is available exactly when you need it.

  2. The bottleneck path. The total project duration equals the longest chain of dependent tasks (the critical path). If any task on this path slips by 1 day, the whole project slips by 1 day. Tasks not on the critical path have slack — you can delay them within bounds without delaying the project.

Both questions are linear-time on the DAG. The dependency graph is acyclic by construction (you can’t have circular prerequisites), so topological order exists, and processing in that order means every value you read from a predecessor is already finalised. There’s no need for Dijkstra’s “settle the closest unvisited vertex” iteration because topological order pre-commits the visit order.

For shortest paths, the same logic holds with min instead of max. Both work even with negative edge weights, because the absence of cycles means there’s no way for a sequence of relaxations to loop back and lower a distance further.

2. Tiny Worked Example

Consider this DAG with edge weights (durations or costs):

        2          4
   A ───────► B ───────► E
   │  3       │ -1     ↗
   ▼          ▼      ↗ 6
   C ───────► D ────
        1          2
                ↘ 3
                  F

Edges: A→B(2), A→C(3), B→D(-1), B→E(4), C→D(1), D→E(6), D→F(3), E→F(2)

(Wait, that has E→F=2, D→F=3, both reach F. Let me fix and re-label edges cleanly.)

Vertices: A, B, C, D, E, F
Edges:
  A → B  weight  2
  A → C  weight  3
  B → D  weight -1
  B → E  weight  4
  C → D  weight  1
  D → E  weight  6
  D → F  weight  3
  E → F  weight  2

A valid topological order: A, B, C, D, E, F (every edge u → v has u before v).

Shortest path from A

Initialise: dist = {A: 0, B: ∞, C: ∞, D: ∞, E: ∞, F: ∞}.

Process in topo order:

  • Process A (dist[A] = 0):
    • Relax A→B: dist[B] = min(∞, 0 + 2) = 2.
    • Relax A→C: dist[C] = min(∞, 0 + 3) = 3.
  • Process B (dist[B] = 2):
    • Relax B→D: dist[D] = min(∞, 2 + (-1)) = 1.
    • Relax B→E: dist[E] = min(∞, 2 + 4) = 6.
  • Process C (dist[C] = 3):
    • Relax C→D: dist[D] = min(1, 3 + 1) = 1. (no improvement)
  • Process D (dist[D] = 1):
    • Relax D→E: dist[E] = min(6, 1 + 6) = 6. (no improvement)
    • Relax D→F: dist[F] = min(∞, 1 + 3) = 4.
  • Process E (dist[E] = 6):
    • Relax E→F: dist[F] = min(4, 6 + 2) = 4. (no improvement)
  • Process F: no outgoing edges.

Final shortest distances from A: {A: 0, B: 2, C: 3, D: 1, E: 6, F: 4}. The shortest path A→F is A → B → D → F with cost 2 + (-1) + 3 = 4. Notice the path uses the negative edge B→D — Dijkstra would silently fail here.

Longest path from A

Initialise: dist = {A: 0, B: -∞, C: -∞, D: -∞, E: -∞, F: -∞} (or 0 if we allow ignoring unreachable nodes — depends on problem).

Process in topo order with max instead of min:

  • Process A:
    • Relax A→B: dist[B] = max(-∞, 0 + 2) = 2.
    • Relax A→C: dist[C] = max(-∞, 0 + 3) = 3.
  • Process B:
    • Relax B→D: dist[D] = max(-∞, 2 + (-1)) = 1.
    • Relax B→E: dist[E] = max(-∞, 2 + 4) = 6.
  • Process C:
    • Relax C→D: dist[D] = max(1, 3 + 1) = 4. Improvement!
  • Process D:
    • Relax D→E: dist[E] = max(6, 4 + 6) = 10. Improvement!
    • Relax D→F: dist[F] = max(-∞, 4 + 3) = 7.
  • Process E:
    • Relax E→F: dist[F] = max(7, 10 + 2) = 12. Improvement!
  • Process F: done.

Final longest distances from A: {A: 0, B: 2, C: 3, D: 4, E: 10, F: 12}. The longest path A→F is A → C → D → E → F with cost 3 + 1 + 6 + 2 = 12.

If A→F represents project completion time and all edges represent task durations on dependency edges, then 12 is the project’s earliest completion time (the duration of the critical path).

3. Pseudocode

Shortest path

dag_shortest_path(graph, source):
    order := topological_sort(graph)
    dist := map; dist[v] := ∞ for every v; dist[source] := 0
    for each u in order:
        if dist[u] == ∞:
            continue                            # u unreachable from source
        for each (v, w) in adjacency(u):
            if dist[u] + w < dist[v]:
                dist[v] := dist[u] + w
    return dist

Longest path

dag_longest_path(graph, source):
    order := topological_sort(graph)
    dist := map; dist[v] := -∞ for every v; dist[source] := 0
    for each u in order:
        if dist[u] == -∞:
            continue
        for each (v, w) in adjacency(u):
            if dist[u] + w > dist[v]:
                dist[v] := dist[u] + w
    return dist

The two algorithms differ in two characters: < becomes >, ∞ becomes -∞ (initialisation). Everything else is identical, because the topological-order guarantee — every predecessor of a vertex is already finalised when the vertex is processed — works the same for min and max.

4. Python Implementation

from collections import defaultdict, deque
 
def topological_sort_kahn(graph):
    """Returns a topological order of vertices, or [] if cycle detected."""
    indeg = defaultdict(int)
    for u in graph:
        indeg[u]                                # ensure all keys exist
        for v, _w in graph[u]:
            indeg[v] += 1
    q = deque(u for u in graph if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v, _w in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) != len(graph):
        return []                                # cycle => not a DAG
    return order
 
def dag_shortest_path(graph, source):
    """
    graph: dict node -> list of (neighbour, weight). Must be a DAG.
    Returns: dict node -> shortest path cost from source (or float('inf')).
    """
    order = topological_sort_kahn(graph)
    if not order:
        raise ValueError("Graph contains a cycle; not a DAG.")
    INF = float('inf')
    dist = {v: INF for v in graph}
    dist[source] = 0
    for u in order:
        if dist[u] == INF:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist
 
def dag_longest_path(graph, source):
    order = topological_sort_kahn(graph)
    if not order:
        raise ValueError("Graph contains a cycle; not a DAG.")
    NINF = float('-inf')
    dist = {v: NINF for v in graph}
    dist[source] = 0
    for u in order:
        if dist[u] == NINF:
            continue
        for v, w in graph[u]:
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
    return dist

Path reconstruction

def dag_longest_path_with_route(graph, source):
    order = topological_sort_kahn(graph)
    NINF = float('-inf')
    dist = {v: NINF for v in graph}
    parent = {v: None for v in graph}
    dist[source] = 0
    for u in order:
        if dist[u] == NINF:
            continue
        for v, w in graph[u]:
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
    return dist, parent
 
def reconstruct(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

5. Complexity

For a DAG with V vertices and E edges:

  • Topological sort: O(V + E) (Kahn’s algorithm: each vertex enqueued/dequeued once, each edge examined once when decrementing in-degree).
  • Relaxation pass: O(V + E) — outer loop V iterations, inner loop totals E edge examinations across all iterations.
  • Total: O(V + E).
  • Space: O(V + E) for the graph itself, O(V) for dist, order, indeg.

Compare to alternatives

SettingBest algorithmComplexity
DAG, any weightsTopological-order relaxationO(V + E)
General graph, non-negative weightsDijkstra’s AlgorithmO((V+E) log V)
General graph, possibly negative weightsBellman-FordO(V·E)
All-pairs, denseFloyd-WarshallO(V³)
Longest path, DAGTopological-order relaxationO(V + E)
Longest path, general graphNP-hardNo polynomial algorithm known

The asymmetry between “longest path is O(V+E) on DAGs” and “longest path is NP-hard on general graphs” is striking. The next section explains why.

6. Why Longest Path on a DAG is Easy but on General Graphs is NP-Hard

On a DAG: there is no way to “loop back” and increase a path’s length by traversing a cycle. The longest path from s to v is finite and equals max over all paths, and that maximum is achieved by some specific (acyclic, by virtue of the DAG) path. Topological-order relaxation finds it in linear time.

On a general graph: longest simple path (no vertex repeated) is the relevant problem; without the simple-path constraint, the longest path is infinite for any graph with a positive-cost cycle. Longest simple path is NP-hard because it generalises Hamiltonian Path — Wikipedia states the connection directly: “a graph G has a Hamiltonian path if and only if its longest path has length n − 1, where n is the number of vertices in G” (per Wikipedia: Longest path problem). So an unweighted longest-simple-path decision oracle solves Hamiltonian Path, and Hamiltonian Path is one of Karp’s original 21 NP-complete problems (catalogued as problem GT39 in Garey & Johnson 1979). Therefore longest simple path is NP-hard.

The DAG structure breaks this hardness because acyclicity makes “simple path” automatic — every path in a DAG is simple — and topological order makes dynamic programming trivial.

Equivalent formulation: longest path on a DAG = shortest path with all weights negated. Wikipedia confirms this reduction explicitly: “if G is a directed acyclic graph (DAG), then no negative cycles can be created, and a longest path in G can be found in linear time by applying a linear time algorithm for shortest paths in −G” (per Wikipedia: Longest path problem). So if we have shortest-path-on-DAG in linear time, we get longest-path-on-DAG in linear time for free. This trick does not work on general graphs: negating weights creates negative cycles, which makes shortest path also NP-hard (or even ill-defined, since you can loop arbitrarily many times to make the path arbitrarily short).

7. Why Negative Weights Are Fine on DAGs

Dijkstra fails with negative weights because its greedy commitment (“settle the closest unsettled vertex”) is unsafe — a longer-then-negative detour might beat the direct route, and once we’ve settled a vertex we don’t reconsider it.

DAG relaxation has no such commitment: it processes every vertex once in topological order, and for each it relaxes all outgoing edges. Negative weights simply mean “this edge subtracts from the path total”; the relaxation dist[v] = min(dist[v], dist[u] + w) works whether w is positive, zero, or negative.

The reason DAGs avoid the Bellman-Ford-like need for V-1 rounds of relaxation is the topological order: by the time we process u, every predecessor of u has already been processed, so dist[u] is finalised at that moment. We can immediately use it to relax u’s outgoing edges. On a general graph there’s no such ordering — predecessors can mutually depend on each other through cycles — so Bellman-Ford pessimistically does V-1 rounds.

The acyclicity guarantee is doing all the work. Lose it, and the algorithm breaks (you’d loop forever attempting to topologically sort a cyclic graph).

8. Critical Path Method (CPM) — The Canonical Application

CPM, introduced by Kelley & Walker (1959) at DuPont and Remington Rand for project scheduling, is the longest-path-on-DAG algorithm dressed up with project-management terminology. The setup:

  • Each task is a vertex (or, in some formulations, an edge).
  • Each dependency (“task X must finish before task Y starts”) is a directed edge.
  • Each task has a duration.

The algorithm computes:

  1. Earliest start (ES) and earliest finish (EF) of each task — by forward DAG longest-path traversal from a virtual “project start” node.
  2. Latest start (LS) and latest finish (LF) of each task — by reverse DAG longest-path traversal from a virtual “project end” node.
  3. Slack (LS − ES) for each task — the amount the task can be delayed without delaying the project.
  4. The critical path — the chain of tasks with zero slack. Delaying any of these by Δ delays the project by exactly Δ.

CPM is taught in every operations-research and project-management course; it remains the standard for construction, manufacturing, software-release planning, and military logistics. The fundamental algorithm is exactly the DAG longest-path relaxation in §3.

9. Other Use Cases

9.1 Build-system time estimation (Bazel, Buck, Make, Ninja)

A build’s task DAG has source files and intermediate artifacts as vertices and “task T must run before task T'” dependencies as edges. Task durations come from historical profiling. The earliest the final binary can be ready = longest path from sources to root = critical path of the build. Bazel’s --profile output explicitly visualises the critical path.

If a developer wants to know “how much would parallel build improve over serial?”, the answer is total_work / critical_path_length — both quantities computable in O(V + E) from the DAG.

9.2 Gate-level circuit timing analysis

A digital circuit’s gates form a DAG (combinational logic, no feedback loops). Each gate has a propagation delay. The circuit’s clock period is bounded below by the longest signal-propagation path through the combinational logic — the critical timing path. Static Timing Analysis (STA) tools (Synopsys PrimeTime, Cadence Tempus) run essentially this DAG-longest-path computation across billions of gates.

9.3 Computational dependency graphs (TensorFlow, PyTorch, Spark)

Dataflow systems represent computation as DAGs. Optimising the schedule across heterogeneous compute (GPU vs CPU, fast vs slow tensors) starts from longest-path analysis of the DAG to identify which kernels lie on the critical path and deserve optimisation budget.

9.4 Course scheduling and degree planning

Course prerequisites form a DAG. The “minimum number of semesters to graduate, taking up to K courses at a time” is a constrained scheduling problem; in the unconstrained limit (K = ∞), it’s exactly DAG longest path = depth of the prerequisite tree.

9.5 Dynamic programming as DAG-shortest-path

Many DP problems are equivalent to shortest path on an implicit DAG: state = subproblem; edge = transition; weight = cost of taking that transition. Coin change, edit distance, longest common subsequence, knapsack — all are DAG shortest/longest path problems if you draw the state graph.

The connection is precise: any DP recurrence with no circular dependencies (which is essentially every DP) can be evaluated by topologically sorting the subproblem-dependency graph and processing in that order. This is why iterative DP is sometimes called “tabulation in topological order.”

10. Variants

10.1 Path counting on a DAG

Same algorithm shape, but count[v] = sum of count[u] over predecessors u (initialised count[source] = 1). Counts the number of distinct source-to-v paths in O(V + E). Common in interview problems (“how many ways to reach the goal”).

10.2 Most-cost-effective subpath

Variants like “longest path with at most K edges” or “longest path with constraint that some vertex must be visited” usually require a state-augmented DAG: replace each vertex v with K+1 copies (v, 0), (v, 1), ..., (v, K). Run DAG longest path on the augmented graph. Time O((V + E)·K).

10.3 All-pairs shortest paths on a DAG

Run single-source DAG shortest path from each vertex: O(V·(V + E)). For sparse DAGs this beats Floyd-Warshall’s O(V³).

10.4 Negative-cost project scheduling

If a task can be accelerated by paying extra (negative-cost edges in the time-cost trade-off model), CPM extends to the time-cost trade-off problem solvable by linear programming — beyond pure DAG-shortest-path but builds on it.

11. Pitfalls

11.1 Forgetting to verify the graph is a DAG

If you run the algorithm on a graph with a cycle, the topological sort returns an empty list (Kahn’s algorithm) or undefined output (DFS-based). The relaxation pass then misses cycles’ vertices entirely, producing silent wrong answers. Always validate or detect:

order = topological_sort_kahn(graph)
if len(order) != len(graph):
    raise ValueError("Graph contains a cycle")

The topological sort starts with all in-degree-zero vertices. If your search source has nonzero in-degree (i.e., other vertices point to it), it still gets sorted into a valid position — but vertices before it in the topo order have dist = ∞ and are correctly skipped. Don’t conflate “topological source” (in-degree 0) with “BFS/DFS source” (where you start the search).

11.3 Negative weights with longest path mistake

Some interviewers ask longest-path on DAG with negative weights as a curveball. The algorithm still works (relaxation with > is sound), but the natural “ignore unreached vertices” check if dist[u] == -∞ is correct only because we initialise to -∞. If a careless implementation initialises to 0 or some other value, negative-weight relaxations break.

11.4 Off-by-one between “vertex weights” and “edge weights”

Some DAG-DP problems put weights on vertices (e.g., task durations on the task itself), not edges. Adapt by either pre-processing (split each vertex into v_in and v_out with an internal edge of weight dur(v)) or by including the vertex weight in the relaxation formula dist[v] = max(dist[u] + edge(u,v) for u in pred(v)) + dur(v).

11.5 Reverse-graph confusion in CPM

The latest-start computation processes vertices in reverse topological order. A common bug is forgetting to reverse the order, which gives wrong slack values for all but the project-end task.

11.6 Multiple critical paths

If two distinct paths achieve the same maximum length, both are critical. Algorithms that track only one parent miss the alternates. For project planning, knowing all critical paths matters because optimising any single one might still leave the project on a different critical path. To enumerate, store all parents that achieve the max instead of just one.

11.7 Using Dijkstra by reflex

A surprising number of candidates reach for Dijkstra on DAG problems. Dijkstra works (it doesn’t need acyclicity, just non-negative weights) but is strictly slower (O((V+E) log V) vs O(V+E)) and wrong on negative weights. If you spot DAG, mention “topological-order relaxation is asymptotically better than Dijkstra here” — interviewer points.

11.8 Floyd-Warshall on a DAG

Same as the above — Floyd-Warshall’s O(V³) is gross overkill on a sparse DAG when V × DAG-DP is O(V·(V+E)).

12. Diagram — Topological Order Determines Visit Order

flowchart LR
  A[A<br/>dist=0] -->|2| B[B<br/>dist=2]
  A -->|3| C[C<br/>dist=3]
  B -->|-1| D[D<br/>dist=1<br/>shortest]
  C -->|1| D
  B -->|4| E[E<br/>dist=6]
  D -->|6| E2[E LP=10<br/>longest]
  D -->|3| F[F<br/>dist=4]
  E -->|2| F2[F LP=12<br/>longest]

What this diagram shows. A DAG with negative-weight edge B→D(-1). Vertices are processed in topological order A, B, C, D, E, F. By the time we process D, both predecessors B and C have already been finalised (dist[B]=2, dist[C]=3), so the relaxation dist[D] = min(2 + (-1), 3 + 1) = 1 for the shortest case (or max(2 + (-1), 3 + 1) = 4 for the longest case) uses correct, finalised predecessor values.

For longest path (right side of each pair), the chain A → C → D → E → F accumulates 3 + 1 + 6 + 2 = 12 — the critical path of the DAG. Dijkstra cannot solve the longest case (would need negation, creating negative weights, which Dijkstra can’t handle). Bellman-Ford would work but in O(V·E) instead of O(V+E).

The key insight: the topological order pre-commits the visit sequence, eliminating the need for a priority queue or repeated relaxation rounds. This is why DAG shortest/longest path is asymptotically faster than every general-graph alternative.

13. Common Interview Problems

ProblemWhy DAG SP/LP fits
LC 329 — Longest Increasing Path in a MatrixEach cell → DAG node; edge from a to b if b > a; longest path = answer
LC 1059 — All Paths from Source Lead to DestinationDAG path enumeration / cycle check
LC 1857 — Largest Color Value in a Directed GraphDAG DP over topological order with per-color count
LC 2050 — Parallel Courses IIICritical path in course-prerequisite DAG with task durations
LC 1494 — Parallel Courses IIDAG scheduling with capacity constraints (harder; pure DAG-LP doesn’t suffice)
LC 851 — Loud and RichDAG DP via topological order
LC 1136 — Parallel Courses (premium)Minimum semesters = longest path on DAG of prerequisites
LC 1235 — Maximum Profit in Job SchedulingDAG over time-sorted jobs; longest path = max profit
LC 1857 / 2050 againBoth are CPM in disguise

The interview tell: the problem features dependency / prerequisite / “must come before” relationships and asks for a min/max of path-additive cost. If you spot it’s a DAG, propose topological-order relaxation; you’ll save a log V factor over Dijkstra.

14. Open Questions

  • How does DAG SP/LP interact with online graph updates? Adding an edge that creates a cycle invalidates the algorithm; adding an edge within the existing DAG can require partial re-computation. Quantify.
  • Are there approximation algorithms for longest simple path on general graphs that match the DAG result asymptotically? (No general-purpose poly-time solution; PTAS exists for specific graph classes.)
  • What’s the right way to handle very large DAGs that don’t fit in memory (out-of-core CPM)?

15. See Also

Graph View

Backlinks