Dijkstra's Algorithm in Coding Interviews: How to Recognize It and Code It Cleanly

Shortest-path questions show up in coding interviews more often than many candidates expect: network delay, cheapest flights, minimum effort paths in a grid. Most of them reduce to Dijkstra's algorithm. The hard part is usually not the code but noticing that the problem is a weighted shortest-path problem in disguise.

How to recognize a Dijkstra problem

If weights can be negative, say so out loud and mention Bellman-Ford instead. Interviewers like hearing that you know where an algorithm breaks.

A clean template

import heapq

def dijkstra(n, adj, src):
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue          # stale entry, skip it
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

The if d > dist[u]: continue line is the detail interviewers watch for. Python's heap has no decrease-key, so you push duplicates and discard the stale ones when they are popped.

Complexity to state

With a binary heap the running time is O((V + E) log V) and the extra space is O(V + E). For a grid of R by C cells, V is R times C and E is about 4V.

Common variations

How to talk through it

Start by naming the graph: what the nodes are, what the edges are, and why the weights are non-negative. Then explain the greedy invariant: the first time a node is popped, its distance is final. Finish with complexity and one edge case, such as unreachable nodes that keep an infinite distance.

Practicing the explanation out loud matters as much as the code. Disclosure: I work on Linkjob AI, an interview preparation tool, but the template above is all you need to handle most shortest-path questions.