Shortest Path in Directed Acyclic Graph

Topological order first, then relax every edge exactly once

time O(V + E)space O(V + E)

A cycle is what forces algorithms like Dijkstra's to keep revisiting vertices — without one, there is a processing order where every vertex's predecessors are always handled first. That order is exactly a topological sort. Walk it once, and the moment you arrive at a vertex its distance can never improve again, so a single relaxation pass over its outgoing edges is enough — no priority queue, and it even works with negative weights since nothing here depends on picking the globally closest vertex next. The badge on each vertex below is its current best-known distance from the source; the highlighted arrows show which edges were just relaxed.

Details

Animated on: 6 vertices, directed weighted edges 0->1(5), 0->2(3), 1->3(6), 2->4(4), 3->5(1), 4->5(1), source = 0 — find the shortest distance from 0 to every other vertex.

Problem:Shortest Path in Directed Acyclic GraphMedium

Topological order first, then relax every edge exactly once

step 1 / 9

The DAG and its edge weights

inf

6 vertices, weighted directed edges, no cycles — that last part is what makes this solvable without a priority queue. If we process vertices in an order where every predecessor comes before its successors, each vertex's distance is final the moment we reach it.

Pseudocode

1FUNCTION shortestPathDAG(n, edges, source):
2  FOR c FROM 0 TO n - 1
3    APPEND EMPTY LIST TO adj[c]
4  FOR EACH (u, v, w) IN edges
5    APPEND (v, w) TO adj[u]
6  order <- TOPOLOGICAL SORT OF (n, adj)
7  dist <- ARRAY OF n VALUES = INFINITY
8  dist[source] <- 0
9  FOR EACH u IN order
10    IF dist[u] != INFINITY
11      FOR EACH (v, w) IN adj[u]
12        dist[v] <- MIN(dist[v], dist[u] + w)
13  RETURN dist

← / → step · space play · Home restart

Every step in words

Show all 9 steps

6 vertices, weighted directed edges, no cycles — that last part is what makes this solvable without a priority queue. If we process vertices in an order where every predecessor comes before its successors, each vertex's distance is final the moment we reach it.
DFS finishes vertices in this order (reversed): 0, 2, 4, 1, 3, 5. Processing them in this order guarantees every edge is relaxed AFTER the vertex it starts from has its final distance.
0's distance is final at 0, since topological order already finished every vertex that could reach it. Relax its edges: 0->1 costs 0+5=5, beating inf; 0->2 costs 0+3=3, beating inf.
2's distance is final at 3, since topological order already finished every vertex that could reach it. Relax its edges: 2->4 costs 3+4=7, beating inf.
4's distance is final at 7, since topological order already finished every vertex that could reach it. Relax its edges: 4->5 costs 7+1=8, beating inf.
1's distance is final at 5, since topological order already finished every vertex that could reach it. Relax its edges: 1->3 costs 5+6=11, beating inf.
3's distance is final at 11, but none of its outgoing edges beat a distance already recorded for their target.
5's distance is final at 8. It has no outgoing edges, so there is nothing to relax.
Every vertex was processed exactly once in topological order: [0, 5, 3, 11, 7, 8] from source 0. The highlighted arrows are the edge that set each vertex's final distance. RETURN dist.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Shortest Path in Directed Acyclic Graph in the editor All Graph problems Back to roadmap