Shortest path in DAG

Hard

Topological order lets you relax each edge once

Problem

Return shortest paths from a source in a weighted DAG.

In simple words

Process nodes in topological order, relaxing edges — no revisits needed in a DAG.

The idea

A DAG has no cycles, so its nodes line up in a topological order where every edge points forward. Walk the nodes in that order and relax each edge exactly once — by the time you reach a node, its distance is already final. No priority queue needed, so it runs in a clean O(V+E), even faster than Dijkstra.

The trick

In topological order dist[u] is final before you relax u's edges, so one pass suffices — no heap, no revisits.
This only works because a DAG has no cycles to send you backwards.

←→stepspaceplay

dist[0, ∞, ∞, ∞, ∞]

topo0 1 2 3 4

1/8

Optimal

timeO(V+E)spaceO(V)

1dist[src] = 0, all others = ∞;  topo = topological order2for u in topo:3  for each edge (u → v, w):  dist[v] = min(dist[v], dist[u] + w)4return dist

Input

nodes: 5, 6 edges

Memory

dist: [0, ∞, ∞, ∞, ∞]
topo: 0 1 2 3 4

Output

shortest dist: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n=6, edges=[[0,1,2],[0,4,1],[4,5,4],[4,2,2],[1,2,3],[2,3,6],[5,3,1]], src=0
Output:: [0, 2, 3, 6, 1, 5]
Explanation:: Topological order lets one clean pass find all distances.

Example 2

Input:: n=2, edges=[[0,1,7]], src=0
Output:: [0, 7]
Explanation:: 0→1 = 7.

Example 3

Input:: n=3, edges=[[0,1,1],[1,2,1]], src=0
Output:: [0, 1, 2]
Explanation:: 0,1,2.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.