DAG Shortest Paths

A directed acyclic graph (DAG) is a directed graph with no directed cycles. This acyclicity is exactly what makes the single-source shortest-paths (SSSP) problem easy: in a DAG, vertices can be linearly ordered so that every edge points "forward" in the order. This ordering is a topological sort — a sequence $v_1, v_2, \dots, v_n$ of the vertices such that for every edge $(u,v)$, $u$ precedes $v$ in the sequence. The key structural fact is this: if edges only point forward in an order, then by the time we reach vertex $v_i$ in that order, every edge entering $v_i$ comes from some $v_j$ with $j < i$, which has already been fully processed. This lets us finalize each vertex's shortest-path distance the moment we visit it, using edge relaxation: for an edge $(u,v)$ with weight $w(u,v)$, we test whether reaching $v$ via $u$ improves on our current best estimate,

The optimal substructure of shortest paths guarantees that a shortest path decomposes into shortest sub-paths of its prefixes; combined with the topological order, this means once all predecessors of $v$ have their final distances, one relaxation of every incoming edge is enough to determine $v$'s final distance. No vertex needs to be revisited, and there is no need to track "visited" sets or manage a priority queue as in Dijkstra's algorithm — the topological order is the priority order, computed once, up front, for free of any weight comparisons. Because correctness never depends on comparing or bounding edge weights (only on the order in which vertices are processed), negative weights cause no difficulty — a decisive advantage over Dijkstra's algorithm, which can produce wrong answers in the presence of negative edges.

The algorithm has three phases: 1. Topologically sort the vertices of the DAG (via DFS finish-time ordering or Kahn's algorithm), both $O(V+E)$. 2. Initialize $d[s] = 0$, $d[v] = +\infty$ for all $v \neq s$, and $\pi[v] = \text{NIL}$. 3. Process vertices in topological order; for each vertex $u$, relax every outgoing edge $(u,v)$. Vertices unreachable from $s$ (topologically before $s$, or in a disconnected part of the DAG) simply never get their $d$-value improved and correctly remain at $+\infty$. ``` DAG-SHORTEST-PATHS(G, w, s): topo ← TOPOLOGICAL-SORT(G) // Θ(V + E) for each vertex v in G.V: d[v] ← ∞ π[v] ← NIL d[s] ← 0 for each vertex u in topo, in order: // Θ(V) iterations for each edge (u, v) in G.Adj[u]: // Θ(E) total relaxations RELAX(u, v, w) return d, π

RELAX(u, v, w): if d[v] > d[u] + w(u, v): d[v] ← d[u] + w(u, v) π[v] ← u ``` If $u$ has not yet been reached (`d[u] = ∞`), its outgoing edges are still examined but never improve any `d[v]`, since $\infty + w$ stays $\infty$ (or is simply skipped as an optimization). After the single pass, `d[v]` holds the shortest-path weight from `s` to `v` for every `v`, and the predecessor pointers `π` let you reconstruct any shortest path by walking backward from a target to `s`.

Longest paths in a DAG (e.g., critical-path scheduling) use the identical algorithm with three sign flips: initialize `d[v] = -∞`, use `d[v] < d[u] + w(u,v)` as the relax condition, and take the vertex with maximum `d[v]` as the answer. Equivalently, negate all weights, run the shortest-path version, and negate the result back.

Time complexity. Topological sort takes $\Theta(V+E)$ (a DFS with finish-time ordering, or Kahn's algorithm using in-degree counting). The main loop visits each vertex exactly once and, across all vertices, examines each edge exactly once (each edge $(u,v)$ is relaxed only when its tail $u$ is processed), giving $\Theta(V + E)$ for the relaxation phase. Total time is

This is asymptotically optimal: any correct algorithm must at least read every vertex and edge once, since an unexamined edge could hold an arbitrarily large negative weight that changes the answer.

Space complexity. $\Theta(V)$ for the distance array $d$, predecessor array $\pi$, and the topological order, plus $\Theta(V+E)$ for the input graph itself (typically not counted as "extra" space).

Correctness (proof by induction on topological order). Claim: immediately after vertex $u$ is processed (all its outgoing edges relaxed) in the main loop, $d[u]$ already equals $\delta(s,u)$, the true shortest-path weight from $s$ to $u$ — provided $u$ is reachable from $s$. Base case: the first vertex in topological order that could possibly be reachable is $s$ itself (any predecessor of $s$ would have to precede it in topological order, but if such a predecessor were reachable from $s$ there would be a cycle, contradicting acyclicity — so nothing "before" $s$ in the order can reach it via a path from $s$). We initialize $d[s] = 0 = \delta(s,s)$ directly. Inductive step: consider a vertex $v \neq s$ reachable from $s$, visited at some point in the topological order. By Edge Relaxation and Optimal Substructure, any shortest path $s \leadsto v$ ends with some edge $(u, v)$, and the prefix $s \leadsto u$ must itself be a shortest path to $u$ (optimal substructure of shortest paths — a subpath of a shortest path is itself shortest). Since $(u,v)$ is an edge, $u$ precedes $v$ in the topological order, so by the inductive hypothesis $d[u] = \delta(s,u)$ before $v$ is processed. Because the algorithm processes vertices in topological order, edge $(u,v)$ is relaxed at some point during $u$'s turn — strictly before $v$ is reached in the outer loop. That relaxation enforces

Standard relaxation invariants also give $d[v] \ge \delta(s,v)$ always (relaxation never produces a distance shorter than a real path's weight, by induction on the number of relaxations along any path). Hence $d[v] = \delta(s,v)$ exactly when $v$'s own outgoing edges are processed, completing the induction. $\blacksquare$

Why acyclicity is essential. In a general graph, no linear order can guarantee that all predecessors of every vertex are finalized before that vertex is processed — cycles mean some predecessor relationship is unavoidably "backward" for any fixed ordering. That is precisely why general graphs need either repeated relaxation passes bounded by path length (Bellman-Ford, $O(VE)$) or a greedy priority-queue order that is only valid without negative edges (Dijkstra, $O((V+E)\log V)$). The DAG algorithm sidesteps both costs because the topological order is a valid processing order by definition of acyclicity.

Tradeoffs. The method is strictly less general than Bellman-Ford (it requires acyclicity) but strictly faster and simpler, and unlike Dijkstra it tolerates negative weights without any special handling — because a negative cycle, the only thing that truly breaks shortest paths, cannot exist in a DAG.

Consider the DAG from the figure, with topological order $s, a, b, c, d, e$ and edges:

Initialize $d[s]=0$, all others $=\infty$.

Final result: $d = [s{:}0,\ a{:}5,\ b{:}2,\ c{:}3,\ d{:}9,\ e{:}6]$. Reconstructing the shortest path to $e$: $\pi[e]=c$, $\pi[c]=a$, $\pi[a]=s$, giving $s \to a \to c \to e$ with total weight $5 + (-2) + 3 = 6$ — matching $d[e]$. Note this path uses a negative edge $(a,c)$; Dijkstra's algorithm, applied naively to this same graph, would greedily finalize $b$ (distance 2) before ever discovering that $a$ leads to a cheaper route to $c$ through a negative edge — and could produce wrong answers on graphs where negative edges create such reorderings. The DAG algorithm sidesteps this entirely because it never relies on distances to choose processing order.

The DAG shortest-paths algorithm is a direct descendant of the broader dynamic-programming and shortest-paths tradition. Its clean linear-time form emerges naturally once topological sorting (attributed in modern form to A. B. Kahn, 1962) is combined with the relaxation technique that underlies Bellman-Ford and Dijkstra's algorithms.

Build systems and dependency resolution. Tools like Make, Bazel, and package managers model tasks as a DAG of dependencies; computing the earliest possible completion time (or minimum cost to reach a target artifact) is exactly a longest- or shortest-path computation in topological order.

Compiler instruction scheduling. Basic blocks compiled into data-dependence DAGs use longest-path computations to find the critical path determining minimum schedule length on a pipelined processor.

Project management (PERT/CPM). Critical-path scheduling computes the longest path through a task-precedence DAG to determine the minimum project duration and identify which tasks have zero slack.

Dynamic programming reformulated as graph problems. Many DP recurrences (edit distance, longest common subsequence, matrix-chain multiplication) can be viewed as DAG shortest/longest-path problems over an implicit state graph, and this framing clarifies both correctness (optimal substructure) and complexity.

Version-control and data-lineage graphs. Commit graphs, data-provenance graphs, and workflow orchestration systems (e.g., Airflow-style DAG schedulers) use topological processing for scheduling and impact analysis, closely related in spirit to shortest-path relaxation. This algorithm is also the conceptual stepping stone to Dijkstra's Algorithm: once cycles are allowed, no fixed processing order works for all inputs, so Dijkstra replaces the static topological order with a dynamic greedy order — always expanding the currently-closest vertex — which is valid precisely when weights are non-negative.

:::quiz[In the inductive correctness proof, what guarantees that d[u] is already final when edge (u,v) is relaxed?]

• u is visited before v in topological order, and the inductive hypothesis applies to u ✓
• u always has the smallest distance among unvisited vertices
• u has out-degree 1
• The graph has no negative edges

Ask the tutor: How would this algorithm need to change if the DAG had multiple source vertices with no single starting point?