Shortest Path in a DAG

Shortest Path in a DAG is the problem where graph shortest-paths gets easy. The moment a graph has no cycles, you do not need Dijkstra or Bellman-Ford — a single sweep in the right order does it, even with negative weights.

The slow way first

You could throw Dijkstra at it — that is O((V + E) log V) and, worse, it breaks the moment an edge weight is negative. Bellman-Ford handles negatives but costs O(V·E). Both do real work to figure out which vertex to finalize next.

The question to ask: is there an order in which a vertex's distance is already final by the time I reach it? For a DAG, yes — and finding it is free.

The idea: process in topological order

A DAG can be topologically sorted: arranged in a line so that every edge points from an earlier vertex to a later one. Sweep the vertices in that order and relax each one's outgoing edges (if dist[u] + w < dist[v]: dist[v] = dist[u] + w).

Because no edge ever points backward, once you arrive at a vertex, every edge that could improve it has already been processed. Its distance is final. No priority queue, no repeated passes.

The key insight: the topological order guarantees dist[u] is final before u is used, so one linear pass suffices — and negative weights are fine, since there is no cycle to exploit.

Walk through it

Step through the animation. First we lay out the DAG with dist[S] = 0 and everything else ∞. We compute the topo order S, A, B, C, T, then process each vertex in turn: relaxing S sets A=2, B=4; relaxing A improves B to 3 and sets C=9; relaxing B improves C to 6; relaxing C sets T=8. Each vertex is finalized exactly once.

Pseudocode

dist[v] = +infinity for all v
dist[source] = 0
order = topological_sort(graph)        # every edge points forward in this list
for u in order:
    if dist[u] is +infinity:
        continue                       # u is unreachable, skip it
    for each edge (u -> v) with weight w:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w      # relax the edge
return dist

The Python solution

def shortest_path_dag(graph, source):
    dist = {v: float("inf") for v in graph}
    dist[source] = 0
    order = topological_sort(graph)
    for u in order:
        if dist[u] == float("inf"):
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

• dist starts every vertex at infinity, then pins the source to 0.
• topological_sort returns the vertices so that every edge points forward in the list — that ordering is what makes the rest work.
• We sweep u through order. If dist[u] is still infinity, u is unreachable, so we continue.
• For each outgoing edge u → v of weight w, we relax it: if going through u beats the best known dist[v], we update it.
• Because of the order, no later step can ever improve dist[u] again, so it is final when we leave it.

Complexity

The topological sort is O(V + E) and the relaxation sweep touches each edge exactly once, also O(V + E). We use O(V) extra space for the distance map.

When this pattern shows up

Practice