Dijkstra's Algorithm Interview Questions and Answers: Traces, Complexity, and Edge Cases
Learn to explain, trace, and code Dijkstra's algorithm at a whiteboard. Includes correctness, complexity, path recovery, stale heap entries, and edge cases.
KnowledgeGate Team
Exam prep & CS education

An interviewer asking about Dijkstra's algorithm wants more than “pick the nearest vertex”. State its precondition, trace each relaxation, defend the greedy choice, choose data structures, and explain why negative edges break it. A whiteboard-ready answer you can explain and code.
Dijkstra's algorithm: the 30-second interview answer
What problem does Dijkstra's algorithm solve? For a weighted directed or undirected graph, it finds shortest-path distances from one source to every reachable vertex, provided every edge weight is non-negative. It is a single-source algorithm, not an all-pairs algorithm. If we also maintain a parent map, we can reconstruct an actual shortest path.
The algorithm keeps a tentative distance for every vertex. It repeatedly takes the unsettled vertex u with the smallest tentative distance, finalises that distance, and examines every outgoing edge (u,v). To relax an edge means testing whether the route through u is better: candidate = dist[u] + weight(u,v). If candidate < dist[v], update dist[v] and set parent[v] = u.
The crucial invariant is this: when u is removed with the minimum current key, dist[u] is final. Any later route can add only non-negative weights, so it cannot become cheaper. If you need to place this beside traversal basics first, review Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step.
Dijkstra's algorithm trace: work the graph by hand
Use source A and directed edges A->B=6, A->C=1, C->B=2, C->D=6, C->E=10, B->D=2, B->E=7, and D->E=3. Write distances in (A,B,C,D,E) order.
Popped vertex | Settled set | Distances | Changed parents |
|---|---|---|---|
Initial |
|
| None |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| None |
For example, popping C improves B from 6 to 1+2=3, sets D to 1+6=7, and sets E to 1+10=11. Popping B then improves D to 3+2=5 and E to 3+7=10. Finally, D improves E to 5+3=8.
To reconstruct the path to E, follow parents backwards: E<-D<-B<-C<-A. Reverse that sequence to get A->C->B->D->E. Its cost is 1+2+2+3=8, matching dist[E].
A lazy heap keeps old entries instead of searching the heap to delete them. When (B,6), (D,7), (E,10), or (E,11) later reaches the top, its key differs from the stored distance, so the algorithm skips it. This stale-entry guard prevents obsolete work without affecting the answer.

For more trace-style practice, continue with Dijkstra's Algorithm MCQs: 12 Solved Questions. A focused question set lets you practise routine relaxations and awkward edge cases.
Why Dijkstra's greedy choice is correct
Why can you finalise the minimum-distance vertex? Suppose u has the smallest tentative distance among all unsettled vertices, but some shorter source-to-u path exists. That path must first cross from a settled vertex x to an unsettled vertex y. When x was settled, relaxing x->y made dist[y] no greater than the cost of that path prefix.
All remaining edges on the supposed path have non-negative weights. Therefore, that prefix costs no more than the complete path to u, which was assumed to cost less than dist[u]. We would have dist[y] < dist[u], contradicting the choice of u as the minimum unsettled vertex.
In the trace, once C is popped at distance 1, routes beginning from vertices with current keys 3, 7, and 11 cannot return to C with a cost below 1 by adding non-negative weights. The precise interview claim is “the minimum tentative distance becomes permanent”. Saying only “Dijkstra is greedy” names the method but does not prove it. Equal-length alternatives are harmless, although tie handling can change the chosen parents and shortest-path tree.
Dijkstra with a priority queue: code structure and complexity
Use an adjacency list and a min-heap of (distance, vertex) pairs:
dist[source] = 0; all other dist values = infinity
parent[source] = null
settled[u] = false for every vertex u
push (0, source) into minHeap
while minHeap is not empty:
(poppedDistance, u) = pop minimum
if poppedDistance != dist[u]: continue
if settled[u]: continue
settled[u] = true
for each (v, weight) in adj[u]:
if settled[v]: continue
candidate = dist[u] + weight
if candidate < dist[v]:
dist[v] = candidate
parent[v] = u
push (candidate, v)Use a true min-heap. A max-heap without key inversion chooses the wrong vertex.
With an adjacency list and the lazy duplicate-entry binary heap shown above, the running time is O((V+E) log E) because the heap can hold O(E) entries. For a simple graph, E=O(V^2), so this becomes O((V+E) log V), commonly shortened to O(E log V) for a connected graph. With unbounded parallel edges, retain the log E bound; an indexed decrease-key heap instead gives O((V+E) log V). The graph, distances, parents, and lazy heap together use O(V+E) space. An adjacency matrix with a linear scan for the next vertex takes O(V^2) time and may be sensible for a dense graph.
For path reconstruction, follow parent[target] back to the source and reverse the collected vertices. If dist[target] remains infinity, return “unreachable”. Early stopping when the target is popped is valid only with non-negative weights and after rejecting stale entries.
Negative weights: the counterexample every answer needs
Consider directed edges S->A=2, S->B=5, B->A=-4, and A->T=2. With the settled-vertex semantics shown above, the pop sequence is S(0), A(2), T(4), B(5). When B(5) is popped, B->A is ignored because A is already settled, so the algorithm finishes with dist[T]=4 and reports S->A->T.
But the true shorter path is S->B->A->T, with cost 5+(-4)+2=3. The negative edge reveals a cheaper route to A only after A was treated as final, so the greedy invariant has broken. This graph has no negative cycle. The negative edge alone causes the failure.

Use Bellman-Ford when negative weights may occur and a shortest path remains well-defined. If a negative cycle is reachable, reject the shortest-path request or report the cycle separately. A visited check or duplicate heap entries cannot repair Dijkstra's proof.
Dijkstra interview follow-ups: BFS, Bellman-Ford, MST, and edge cases
Requirement | Suitable algorithm | Key idea |
|---|---|---|
Unweighted or equal-weight edges | BFS | Explore by increasing edge count in |
Weights only | 0-1 BFS | Use a deque |
Arbitrary non-negative weights | Dijkstra | Use minimum tentative distance |
Negative weights allowed | Bellman-Ford | Repeatedly relax every edge |
All-pairs paths on a modest dense graph | Floyd-Warshall | Dynamic programming over intermediate vertices |
Do not confuse a shortest-path tree with a minimum spanning tree. In the undirected triangle A-B=2, A-C=3, B-C=2, Dijkstra from A selects A-B and A-C: the shortest distances are 2 and 3, and those tree edges total 5. An MST selects A-B and B-C, totalling 2+2=4. Dijkstra minimises each distance from one source; an MST minimises the tree's total edge weight.
Also test the implementation boundaries:
A single source vertex has distance
0.A disconnected vertex remains at infinity.
Parallel edges retain the cheaper relaxation.
A zero-weight edge is valid.
The distance type must hold complete path sums without overflow.
Equal shortest paths need an explicit tie policy only when deterministic parents matter.
Dijkstra's algorithm interview answer: the short version and next step
At the whiteboard, use this six-point checklist:
Define the single-source shortest-path problem.
State that all edge weights must be non-negative.
Explain why the minimum tentative distance becomes final.
Show relaxation with
dist[u] + weight(u,v).Choose an adjacency list and min-heap.
Give the complexity and volunteer the negative-edge counterexample.
Trace once before coding, then test parent reconstruction, stale heap entries, and unreachable vertices. The Placement Preparation & Coding provides the wider interview sequence. If you want Dijkstra placed beside other graph and algorithm topics in a structured path, continue with the Algorithms course.
Keep learning
TCS NQT Coding Round Edge Cases: Pre-Submission Test Plan
Use this home-practice plan to expose boundary, duplicate, negative-value, overflow, state-reset, and output-format bugs before you submit code.
Dijkstra's Algorithm MCQs: 12 Solved Questions with Explanations
Solve 12 Dijkstra's algorithm MCQs covering the core idea, a full trace, failure cases, complexity choices and the unweighted special case.
Painter's Algorithm: Depth Sorting, Back-to-Front Rendering and Failure Cases
Learn when far-to-near polygon sorting produces the correct visible surface, why crossings and cycles defeat a global order, and when geometry must be split.
Prim's Algorithm and Minimum Spanning Tree: Worked Example, Complexity and Exam Traps
Learn what makes Prim's greedy choice safe, trace every key update on a six-vertex graph, and avoid the mistakes that derail MST questions.





