Pattern visualizer
Shortest Path in DAG
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. 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..
Topological order first, then relax every edge exactly once
The DAG and its edge weights
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.
1FUNCTION shortestPathDAG(n, edges, source):2 FOR c FROM 0 TO n - 13 APPEND EMPTY LIST TO adj[c]4 FOR EACH (u, v, w) IN edges5 APPEND (v, w) TO adj[u]6 order <- TOPOLOGICAL SORT OF (n, adj)7 dist <- ARRAY OF n VALUES = INFINITY8 dist[source] <- 09 FOR EACH u IN order10 IF dist[u] != INFINITY11 FOR EACH (v, w) IN adj[u]12 dist[v] <- MIN(dist[v], dist[u] + w)13 RETURN dist
← / → step · space play · Home restart