Dijkstra's Algorithm in Coding Interviews: When and How to Use It

Shortest path problems are a staple of technical interviews, and Dijkstra's algorithm is the tool interviewers most often expect for weighted graphs. The good news is that the implementation is short and very consistent across problems. The harder part is recognizing when it applies and explaining why it works. When to reach for Dijkstra Use Dijkstra when: - The graph has weighted edges. - All weights are non-negative. - You need the minimum total cost from one source to other nodes. If all edges have the same weight, plain BFS is simpler and faster. If some weights are negative, Dijkstra can give wrong answers; mention Bellman-Ford instead. Saying this out loud early shows you understand the boundaries of the algorithm. The core idea Dijkstra greedily finalizes the closest unvisited node. Because weights are non-negative, once a node is popped from the priority queue with the smallest known distance, no later path can be shorter. That is the invariant to explain if the interviewer asks why it is correct. The standard implementation 1. Build an adjacency list: for each node, a list of (neighbor, weight). 2. Create a distance map with the source at 0 and everything else at infinity. 3. Push (0, source) into a min-heap. 4. While the heap is not empty, pop (d, node). If d is greater than the recorded distance for node, skip it; this is a stale entry. 5. For each neighbor, compute d + weight. If it is smaller than the neighbor's recorded distance, update it and push the new pair. The "skip stale entries" check is the detail that keeps this lazy version correct without a decrease-key operation, which most languages' heaps do not support. Complexity With a binary heap, the running time is O((V + E) log V). Space is O(V + E) for the graph and heap. Problems to practice - Network Delay Time: the answer is the maximum shortest distance from the source, or -1 if a node is unreachable. - Path With Minimum Effort: the "cost" of a path is its maximum step, not its sum, but the same heap pattern works. - Cheapest Flights Within K Stops: a constraint on the number of edges changes the problem; track (cost, node, stops) and consider a BFS or Bellman-Ford variant. - Swim in Rising Water: another minimax path problem on a grid. - Grid problems with weighted cells: treat each cell as a node and its four neighbors as edges. Common mistakes - Forgetting the stale entry check, which leads to repeated work or wrong answers in some variants. - Using a visited set incorrectly, marking nodes when pushed instead of when popped. - Applying Dijkstra to graphs with negative edges. - Returning early incorrectly: you can stop when you pop the target, but not when you first push it. Follow-up questions - How would you reconstruct the path? Store a parent pointer each time you update a distance. - How does A* differ? It adds a heuristic estimate to the priority so the search moves toward the target. - What if the graph is too large for memory? Discuss bidirectional search or precomputed routing structures. Explaining while you code Name the invariant, describe the heap contents, and trace a tiny example with three or four nodes. If you tend to lose your train of thought when an interviewer is watching, Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, helping you keep your explanation clear.