Dijkstra Shortest Path Interview Pattern
When a graph problem mentions weighted edges and asks for the cheapest or shortest path, Dijkstra is often the right tool—if you recognize it quickly and implement it cleanly. This guide is a practical Dijkstra interview pattern: when to use it, how to narrate it, and which bugs waste the most time.
When Dijkstra vs BFS vs others
| Signal | Prefer | Why |
|---|---|---|
| Unweighted edges (or all weight 1) | BFS | True shortest path in O(V + E) |
| Non-negative weights | Dijkstra | Classic min-cost path |
| Negative weights | Bellman-Ford (or say so) | Dijkstra is incorrect |
| All-pairs | Floyd-Warshall / repeated Dijkstra | Depends on size |
| Grid with uniform step cost | BFS | Don't overcomplicate |
Opening line:
"Edges have non-negative weights and we need the minimum cost from a source, so I'll use Dijkstra with a min-heap."
Core idea in one sentence
Always expand the node with the smallest known distance next. Once a node's distance is finalized (with the standard non-negative-weight assumption), you never need a cheaper path to it.
Template talk track
- Build an adjacency list:
node → list of (neighbor, weight) dist[source] = 0, others∞- Min-heap of
(distance, node) - While the heap is not empty:
- Pop the smallest distance - Skip if this entry is stale (distance > dist[node]) - For each edge, relax: if dist[node] + w < dist[nei], update and push
- Answer is
dist[target]or the fulldistarray
Narrate the stale-entry skip—it prevents subtle wrong answers when you push duplicates instead of decreasing keys.
Complexity sentence (say it early)
"With a binary heap, Dijkstra is O((V + E) log V). Space is O(V + E) for the graph, distances, and heap."
If your language's heap is slow or you re-push often, still state the standard bound and note duplicate heap entries.
Checklist before you code
- [ ] Weights confirmed non-negative
- [ ] Directed vs undirected clarified (add both edges if undirected)
- [ ] Single source vs multi-source (multi-source: push all sources at 0)
- [ ] What to return if unreachable (
-1,∞, or "impossible") - [ ] Ties: any shortest path vs lexicographically smallest path?
Common interview bugs
| Bug | Symptom | Fix |
|---|---|---|
| Using BFS on weighted graph | Wrong costs | Switch to Dijkstra |
| Max-heap by mistake | Explores large distances first | Confirm min-heap ordering |
| Not skipping stale pops | Wrong or slow | Compare popped dist to dist[node] |
| Marking visited too early | Misses cheaper path | Finalize on pop (non-negative weights), not on first push |
| Forgetting undirected reverse edges | Unreachable nodes | Add both directions |
Integer overflow on ∞ + w | Weird distances | Use a large safe sentinel or skip ∞ nodes |
Grid variant
On a grid where moving into a cell costs grid[r][c] (or similar), treat each cell as a node and each move as a weighted edge. Same algorithm; adjacency is implicit via four directions. Mention bounds checks and visited/finalized rules the same way.
Follow-up questions to expect
| Follow-up | Talk about |
|---|---|
| Negative edges | Dijkstra fails; Bellman-Ford or SPFA discussion |
| Rebuild the path | Parent pointers updated on successful relax |
| Early exit | Stop when target is finalized on pop |
| Dense graphs | Consider other priority queue structures; still discuss tradeoffs |
You don't need a thesis—two sentences and a tradeoff are enough.
Mini practice set (pattern quality over quantity)
- Classic weighted shortest path to one target
- Network delay / time for signal to reach all nodes
- Cheapest flights with at most K stops (often a Dijkstra variant or Bellman-Ford-style DP—say which and why)
- Path with minimum effort on a grid (binary search + BFS or Dijkstra—compare)
After each, write one error-log line: what you almost got wrong.
Soft practice note
Dijkstra is mostly implementation discipline under time pressure. Timed, out-loud rehearsal beats reading another explanation. If you want a structured way to practice patterns and stay composed under pressure, Luna Interview is built for rehearsal and prep—before the interview, not as a way around the rules during one.
30-second decision script
- Weighted? If no → BFS
- Negative weights? If yes → not Dijkstra
- Need min cost from a source? → Dijkstra + min-heap
- State complexity, then code relaxations carefully
Master the talk track and the stale-pop check. That's the pattern interviewers actually see.
Rehearse with an AI interview copilot, then browse commonly reported interview questions.