PPractick

The problem

A maps app stores roads as an undirected graph with non-negative travel times and must compute the fastest time from a source to every location. BFS no longer works because edges have different weights. Dijkstra's algorithm always expands the unsettled vertex with the smallest tentative distance. Since weights are non-negative, nothing found later can beat that distance, so it's final. A min-heap of (distance, vertex) pairs makes "smallest tentative distance" fast.

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

Function signature

vector<int> dijkstra(int V, const vector<array<int, 3>>& edges, int src);  // undirected; -1 if unreachable

Test cases

Input (V, edges, src)	Output	Explanation
(3, [[0,1,1],[1,2,3],[0,2,6]], 2)	[4, 3, 0]	2→1→0 beats 2→0
(4, [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], 0)	[0, 3, 1, 4]
(2, [[0,1,9]], 0)	[0, 9]
(3, [[0,1,2]], 0)	[0, 2, -1]	2 is unreachable
(1, [], 0)	[0]

(Confirm: weights are non-negative; edges are undirected; unreachable vertices get −1.)

How interviewers phrase it

• "Given a weighted undirected graph and a source, find the shortest distance from the source to every vertex" (GeeksforGeeks "Implementing Dijkstra Algorithm").

Clarifying questions to ask

1. Are weights non-negative? (Yes, which Dijkstra requires.)
2. Directed or undirected? (Undirected here; the algorithm is identical either way.)
3. How large? (Up to 10⁴ vertices, so a heap is expected.)

Follow-ups to expect

1. "Why must weights be non-negative?"
2. "What's 'lazy deletion'?"
3. "Complexity?"
4. "How do you recover the actual path?"
5. "Negative weights?"

Related questions

• Why priority Queue is used in Djisktra's Algorithm Hard
• Path with minimum effort Hard
• Number of ways to arrive at destination Hard
• Prim's Algorithm Hard
• Network Delay Time Medium
• Swim in Rising Water Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in