PPractick

The problem

A routing team is choosing how to implement Dijkstra for a directed road graph with non-negative weights, and wants to understand why a priority queue is the standard choice. Implement the three classic versions and confirm they agree:

• an array scan that picks the minimum unsettled vertex in O(V), so O(V²) overall
• an ordered set with real decrease-key
• a min-heap with lazy deletion

The heap versions pick the next vertex in O(log V) instead of O(V), which matters for sparse graphs.

Example: 5 vertices, edges 0→1 (10), 0→2 (3), 2→1 (4), 1→3 (2), 2→3 (8), 3→4 (7), source 0 → [0, 7, 3, 9, 16].

Function signature

vector<long long> dijkstraArray(int V, const vector<vector<pair<int, int>>>& adj, int src);  // O(V^2)
vector<long long> dijkstraSet(int V, const vector<vector<pair<int, int>>>& adj, int src);    // O(E log V)
vector<long long> dijkstraHeap(int V, const vector<vector<pair<int, int>>>& adj, int src);   // O(E log V)

Test cases

Input (V, directed edges, src)	Output (all three agree)	Explanation
(5, [[0,1,10],[0,2,3],[2,1,4],[1,3,2],[2,3,8],[3,4,7]], 0)	[0, 7, 3, 9, 16]	1 via 2 costs 7, not 10
(3, [[0,1,1],[1,2,1],[0,2,5]], 0)	[0, 1, 2]
(4, [[0,1,1],[0,2,1],[1,3,1],[2,3,1]], 0)	[0, 1, 1, 2]
(3, [[1,0,1]], 0)	[0, -1, -1]	Edges point the wrong way
(1, [], 0)	[0]

(Confirm: edges are directed with non-negative weights; unreachable vertices print −1.)

How interviewers phrase it

• "Why do we use a priority queue in Dijkstra's algorithm? What would happen with a normal queue, or with a plain array?"

Clarifying questions to ask

1. Dense or sparse graphs? (That decides between the array version and the heap.)
2. Non-negative weights? (Required by every version.)
3. Does the language provide decrease-key? (C++ priority_queue doesn't, hence lazy deletion or set.)

Follow-ups to expect

1. "What does the priority queue buy you?"
2. "When is the O(V²) array version better?"
3. "What happens with a plain FIFO queue?"
4. "Lazy deletion vs set?"
5. "Better heaps?"

Related questions

• Djisktra's Algorithm Hard
• Path with minimum effort Hard
• Number of ways to arrive at destination Hard
• Introduction to Graph Easy
• Network Delay Time Medium
• MST theory Easy

All 474 dsa interview questions

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