Shortest Path in DAG

Given a weighted directed acyclic graph (DAG) with V vertices (0 .. V-1) and edges edges[i] = [u, v, w] (a directed edge u → v of weight w), return an array dist where dist[i] is the shortest distance from source vertex 0 to vertex i, or -1 if i is unreachable.

Hints

· Stuck? Reveal one nudge at a time.

On a DAG you don't need Dijkstra — use a topological order.

Process vertices in topological order and relax each one's outgoing edges.

Every vertex's shortest distance is final by the time you reach it.

Common doubts

In topo order, all paths into a vertex come from earlier-processed vertices, so its distance is already minimal when you relax its edges.

Yes — a DAG has no cycles, hence no negative cycles, so relaxation in topo order stays correct.

When the graph isn't a DAG but has no negative cycle; then no topological order exists.

Interview follow-ups

· What an interviewer asks next.

Store a predecessor for each vertex whenever you relax an improving edge.

Same topo relaxation with max instead of min — longest path is NP-hard on general graphs but linear on a DAG.

Fun facts

DAG shortest path is one of the few shortest-path problems that's linear-time.
The same topological relaxation solves DAG longest path, used in critical-path scheduling.

Asked at

AmazonGoogle

Frequently Sometimes Occasionally

Example 1

Input: V = 4, edges = [[0,1,2],[0,2,4],[1,2,1],[2,3,3]]
Output: [0, 2, 3, 6]
0→1→2→3 gives distances 0,2,3,6 (the 0→2 direct edge of 4 is beaten by 0→1→2 = 3).

Example 2

Input: V = 4, edges = [[0,1,1],[2,3,1]]
Output: [0, 1, -1, -1]
Vertices 2 and 3 are unreachable from 0.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - the graph is a DAG - edges are [u, v, w] directed

On a DAG you don't need Dijkstra or its heap — the acyclicity gives you a topological order in which every vertex's shortest distance is finalised before you process it. So: topologically sort, then walk the vertices in that order and relax each one's outgoing edges (dist[v] = min(dist[v], dist[u] + w)). One pass, O(V + E), and it works even with negative edge weights (no cycles means no negative loops).

The brute alternative is Bellman-Ford — relax all edges V-1 times — which also handles the DAG (indeed any graph without negative cycles) but at O(V·E).

Prerequisites

Before you start

· Concepts used directly in the solution.

Topological order. every predecessor is processed first.

Edge relaxation. dist[v] = min(dist[v], dist[u] + w).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What's the source?”

Vertex 0.

“Unreachable vertices?”

Report -1.

The ideal opening — say it like this

Because it's a DAG I topologically sort, then relax edges in that order so each vertex is finalised once.

That's O(V+E) — no heap needed — and it even tolerates negative weights.

Understand the problem

Worked example — V = 4, edges [[0,1,2],[0,2,4],[1,2,1],[2,3,3]]

topo order 0,1,2,3
0: dist[1]=2, dist[2]=4
1: dist[2]=min(4, 2+1)=3
2: dist[3]=3+3=6
dist = [0, 2, 3, 6]

Key observations

1Aha

Topological order finalises distances

Each vertex's shortest distance is set before it's processed.

2Aha

No heap needed

Order replaces Dijkstra's priority queue on a DAG.

3Aha

Negative weights OK

No cycles ⇒ no negative loops.

Brute force vs optimal

	Bellman-Ford	Topological relaxation
Idea	relax all edges V-1 times	relax edges in topological order once
Time	O(V·E)	O(V+E)
Needs DAG

Both give the same distances; the topological pass is linear. Full code is in the Approaches selector below.

Summary

Key takeaway

Topologically sort the DAG, then relax each vertex's outgoing edges in that order — every distance is finalised in one O(V+E) pass, even with negative weights.

order = toposort(V, edges)
dist[0]=0; for u in order: for (u->v,w): dist[v] = min(dist[v], dist[u]+w)