DSA interview question

Shortest Path in a Directed Acyclic Graph (Weighted)

Hard · Data structures · Topics: graph, dfs, topological sort

The problem

A project plan is a DAG of tasks with weighted edges (u → v with cost w). From the start task 0, we want the cheapest cost to reach every task, or −1 if unreachable. Because there are no cycles, we don't need Dijkstra. Process vertices in topological order and relax their outgoing edges. When a vertex is processed, every path into it has already been considered, so its distance is final. This is O(V + E) and also works with negative weights.

Example: 6 vertices, edges 0→1 (2), 0→4 (1), 4→5 (4), 4→2 (2), 1→2 (3), 2→3 (6), 5→3 (1) → [0, 2, 3, 6, 1, 5].

Function signature

vector<int> shortestPathDAG(int N, const vector<array<int, 3>>& edges);  // source 0; -1 if unreachable

Test cases

Input `(N, edges u, v, w)`	Output	Explanation
`(6, [[0,1,2],[0,4,1],[4,5,4],[4,2,2],[1,2,3],[2,3,6],[5,3,1]])`	`[0, 2, 3, 6, 1, 5]`	3 via 0-4-5-3
`(4, [[0,1,5],[0,2,1],[2,1,1],[1,3,1]])`	`[0, 2, 1, 3]`	The detour via 2 is cheaper
`(5, [[0,1,1],[1,2,1],[0,2,5],[2,3,1],[3,4,1],[0,4,10]])`	`[0, 1, 2, 3, 4]`
`(3, [[1,2,4]])`	`[0, -1, -1]`	Nothing leaves 0
`(1, [])`	`[0]`

(Confirm: the graph is a DAG; the source is vertex 0; weights here are non-negative so −1 can mark "unreachable".)

How interviewers phrase it

"Given a weighted DAG, find the shortest path from source 0 to every vertex" (GeeksforGeeks "Shortest path in Directed Acyclic Graph").

Clarifying questions to ask

Is the graph acyclic? (Yes, which enables the linear-time method.)
Can weights be negative? (The algorithm handles it, as long as there's no cycle.)
What's the source? (Vertex 0.)

Follow-ups to expect

"Why topological order?"
"Why not Dijkstra?"
"Longest path?"
"Unreachable vertices?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview