Shortest path in a directed acyclic graph (DAG) is the minimum-total-weight route from a starting vertex to another vertex when every edge has a direction and the graph contains no directed cycles. Because a DAG can be arranged in topological order, its shortest paths can be calculated in linear time, O(V + E), even when some edge weights are negative.
Introduction
Graph algorithms are often associated with trade-offs: an algorithm may be fast but restricted to positive weights, or flexible but computationally expensive. Shortest-path computation in a DAG avoids that compromise. The absence of cycles creates a natural processing order, allowing each vertex’s optimal distance to be determined before its outgoing edges are examined It's one of those things that adds up. Which is the point..
This property makes DAG shortest-path algorithms valuable in project scheduling, dependency resolution, route planning, compiler optimization, and dynamic programming. Understanding the method also reveals how topological sorting turns a graph problem into an efficient sequence of local decisions.
What Is a Directed Acyclic Graph?
A directed graph consists of vertices connected by edges that point from one vertex to another. An edge from vertex A to vertex B does not imply that an edge from B to A exists The details matter here..
A graph is acyclic when no sequence of directed edges begins and ends at the same vertex. Put another way, it contains no directed cycle.
For example:
A → B → D
↓ ↑
C ────┘
The edges above form a DAG because movement always advances through the graph without returning to an earlier vertex. By contrast, adding an edge from D to A would create a directed cycle.
A DAG can always be placed in a topological order: a linear arrangement in which every directed edge u → v places u before v. Multiple valid orders may exist.
How Edge Weights Affect a Path
Each edge may have a weight representing distance, time, cost, energy consumption, or another quantity. The weight of a path is the sum of the weights of all edges along that path And it works..
Suppose the available routes from A to D are:
A → B → D = 4 + 5 = 9
A → C → D = 2 + 8 = 10
A → C → B → D = 2 + 1 + 5 = 8
The shortest path is A → C → B → D, with total weight 8 Most people skip this — try not to..
Weights may be positive, zero, or negative. Negative weights are valid as long as the graph remains acyclic. Since a DAG has no cycles, it cannot contain a negative-weight cycle that could be traversed repeatedly to reduce a path indefinitely No workaround needed..
The Core Idea: Topological Order Plus Relaxation
The DAG shortest-path algorithm combines two concepts:
- Topological ordering determines a safe processing sequence.
- Edge relaxation updates a destination whenever a better route is found.
To relax an edge u → v with weight w, compare the known distance to v with the distance obtained by traveling through u:
distance[u]
… + w < distance[v] then
distance[v] ← distance[u] + w
predecessor[v] ← u
This simple comparison propagates the best known distance forward through the graph. Because every edge points from an earlier vertex to a later one in a topological order, when we reach *u* we have already finalized the optimal distance to *u*; relaxing its outgoing edges can therefore never be improved later by a different route that would have to pass through a vertex appearing after *u* in the order.
And yeah — that's actually more nuanced than it sounds.
### Algorithm in Pseudocode
function DAG_ShortestPath(G, s): // G = (V, E) directed acyclic graph, edge weight w(u,v) // s = source vertex topo ← TopologicalSort(G) // O(V+E) via Kahn’s or DFS for each v in V: dist[v] ← ∞ pred[v] ← NIL dist[s] ← 0
for u in topo: // respects edge direction
for each (u, v) in E:
w ← weight(u, v)
if dist[u] + w < dist[v]:
dist[v] ← dist[u] + w
pred[v] ← u
return dist, pred
*TopologicalSort* can be implemented with a queue of zero‑in‑degree vertices (Kahn’s algorithm) or with a depth‑first search that records vertices on exit. Both run in linear time.
### Correctness Sketch
We prove by induction on the topological order that after processing a vertex *x*, `dist[x]` equals the weight of the shortest *s → x* path.
*Base*: For the source *s*, `dist[s] = 0`, which is optimal because any non‑empty path would have positive length (or zero if zero‑weight edges exist) and would have to leave *s* and return later, impossible in a DAG.
*Inductive step*: Assume the claim holds for all vertices preceding *y* in the topological order. Any path *s → y* must end with an edge *z → y* where *z* appears before *y*. By the induction hypothesis, when *z* was processed we already had the optimal distance to *z*. The relaxation of *z → y* therefore considered exactly the weight of that optimal prefix plus the edge weight, and stored the minimum over all such predecessors. No later vertex can improve *dist[y]* because any alternative path would have to use an edge entering *y* from a vertex that also precedes *y*, and all those edges have already been relaxed. Hence after *y*’s turn, `dist[y]` is optimal.
By induction, the invariant holds for every vertex, establishing correctness.
### Complexity Analysis
* Topological sorting: O(V + E)
* Single pass over vertices with relaxation of each outgoing edge: O(V + E)
Overall time = O(V + E), space = O(V) for the distance and predecessor arrays plus the topological order.
### Handling Negative Weights
Because a DAG lacks directed cycles, a negative‑weight edge cannot participate in a negative‑weight cycle that would allow arbitrarily short paths. The algorithm therefore works unchanged for negative weights; the only requirement is that the graph remain acyclic.
### Worked Example (continuing the earlier graph)
Vertices: {A, B, C, D}
Edges with weights: A→B (4), A→C (2), B→D (5), C→D (8), C→B (1)
Topological order (one valid): A, C, B, D
Initialize: dist[A]=0, others = ∞
*Process A*: relax A→B → dist[B]=4; relax A→C → dist[C]=2
*Process C*: relax C→B → dist[B]=min(4, 2+1)=3; relax C→D → dist[D]=2+8=10
*Process B*: relax B→D → dist[D]=min(10, 3+5)=8
*Process D*: no outgoing edges
Final distances: dist[A]=0, dist[C]=2, dist[B]=3, dist[D]=8, with