Dijkstra's Shortest Path
Dijkstra finds cheapest paths from one source in graphs with non-negative weights, in O((V+E) log V) with a heap. Run output, a negative-edge failure and timings on graphs up to 400k nodes.
Dijkstra's algorithm finds the cheapest path from one source to every reachable node in a graph with non-negative edge weights. It repeatedly pops the unfinished node with the smallest tentative distance from a min-heap and relaxes its edges, in O((V + E) log V). Interviewers expect the limit: a negative edge breaks it, so use Bellman-Ford instead.
Dijkstra's algorithm finds the cheapest path from one source to every reachable node in a graph with non-negative edge weights. It repeatedly takes the unfinished node with the smallest tentative distance from a min-heap and relaxes its edges, for O((V + E) log V) time.
- Dijkstra's algorithm with a binary heap runs in O((V + E) log V); with a plain array instead of a heap it is O(V squared), which can win on dense graphs.
- Python's heapq has no decrease-key, so Dijkstra implementations push a new entry on each improvement and skip stale entries when they are popped.
- On the graph S to A 2, S to B 5, B to A -10, A to T 1, a visited-set Dijkstra returned A = 2 and T = 3, while the true distances are -5 and -4.
- A Python Dijkstra on a random graph with 100,000 nodes and 300,000 edges took 0.41 s and 111,481 heap pops in one run.
- For graphs with negative edge weights, Bellman-Ford runs in O(V times E) and can also detect negative cycles.
01What Dijkstra's algorithm solves
You have a weighted graph, a start node, and you want the cheapest total weight to reach every other node: road distances, network latency, the cost of a flight route. BFS only counts edges, so it gives the right answer when every edge costs 1 and the wrong one otherwise.
Dijkstra's algorithm handles arbitrary non-negative weights. The idea: keep a tentative distance for every node, always finalise the unfinalised node with the smallest tentative distance, and use it to improve its neighbours. Because no edge can have negative cost, a node with the smallest tentative distance cannot be improved later by going through some other unfinished node, so its distance is final the moment you pick it.
02The algorithm with a heap
import heapq
def dijkstra(graph, src):
dist = {src: 0}
prev = {}
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float("inf")):
continue # stale entry
for v, w in graph.get(u, []):
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
prev[v] = u
heapq.heappush(pq, (nd, v))
return dist, prevPython's heapq has no decrease-key operation, so the code pushes a new, better entry and ignores the old one when it surfaces. That is the "stale entry" check, and the heapq documentation describes the same idea for changing priorities.
Run on this graph, A to B 4, A to C 1, C to B 2, C to D 7, B to E 3, E to D 2, E to F 5, D to F 1, the output is {'A': 0, 'B': 3, 'C': 1, 'D': 8, 'E': 6, 'F': 9}. Walking prev back from F gives A, C, D, F. Note the shortcut: the direct edge A to B costs 4, but A to C to B costs 3, and the algorithm finds it. D is reachable at cost 8 two ways (via C, or via B and E), so a tie there is normal and either path is correct.
03Why it is right, and why negative edges break it
The correctness argument is the one in the first section: the smallest tentative distance is already optimal because any other route to that node must pass through a node with an equal or larger tentative distance and then add a non-negative weight.
A negative edge removes that guarantee. Here is a concrete failure. Graph: S to A 2, S to B 5, B to A -10, A to T 1. The true distance to A is 5 + (-10) = -5 and to T is -4. A textbook version that marks nodes done once popped:
def dijkstra_visited(graph, src):
dist = {src: 0}; done = set(); pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if u in done: continue
done.add(u)
for v, w in graph.get(u, []):
if v not in done and d + w < dist.get(v, float("inf")):
dist[v] = d + w; heapq.heappush(pq, (d + w, v))
return distreturns {'S': 0, 'A': 2, 'B': 5, 'T': 3}. Both A and T are wrong. My earlier version without the done-set happened to get this particular graph right, because it re-pushes A when it improves, but it then re-processes nodes and loses the O((V + E) log V) bound, so do not rely on that. For graphs with negative edges use Bellman-Ford, O(V times E), or Johnson's algorithm for all pairs.
04Complexity and measured behaviour
Each edge can cause one push and each push one pop, and each heap operation is O(log V), giving O((V + E) log V). Using a Fibonacci heap improves the bound in theory to O(E + V log V), but binary heaps are usually faster in practice because of constants.
I measured it on random directed graphs with 3 outgoing edges per node and weights 1 to 100 (Python 3.13, one run each, so treat the times as rough):
- V = 10,000, E = 30,000: 11,147 heap pops, 0.02 s
- V = 100,000, E = 300,000: 111,481 pops, 0.41 s
- V = 400,000, E = 1,200,000: 445,306 pops, 2.51 s
The pops are a bit above the reachable node count (9,387, 94,167 and 376,031), the extra being stale entries. Time grew faster than linearly: 10 times the nodes took about 20 times as long (0.02 s to 0.41 s). The log factor and memory cache misses on larger dicts are plausible causes, but I did not isolate them.
On the correctness side, I compared against a plain Bellman-Ford on 500 random graphs of up to 40 nodes and the distance maps matched every time.
05Rebuilding the path and common variants
To get the route and not only the cost, record prev[v] = u on every improvement and walk back from the destination:
def path(prev, src, dst):
out = [dst]
while out[-1] != src:
out.append(prev[out[-1]])
return out[::-1]If you need a single destination, return as soon as you pop it, because its distance is final at that moment. A* adds an estimate of the remaining distance to the priority and is Dijkstra with a guiding heuristic; with a heuristic of zero it is exactly Dijkstra. For an unweighted graph, plain BFS is simpler and O(V + E). For graphs where weights are only 0 or 1, a deque-based 0-1 BFS beats a heap.
Unreachable nodes never enter dist, so check membership before reading it, which is a common source of KeyError in interview code.
06Common interview questions
Q: What is the time complexity of Dijkstra with a binary heap?
A: O((V + E) log V). With a simple array instead of a heap it is O(V squared), which can win on dense graphs.
Q: Why does Dijkstra fail with negative edges?
A: It assumes a popped node's distance is final. A later negative edge can improve it, but the node is already processed.
Q: Why do we skip stale heap entries?
A: The heap has no decrease-key, so improved distances are pushed again, and older larger entries must be ignored when they pop.
Q: How do you recover the actual path?
A: Keep a predecessor map updated on each improvement and walk back from the target.
Q: BFS or Dijkstra?
A: BFS when all edges cost the same, Dijkstra when weights differ and are non-negative.
Q: What if weights can be negative?
A: Bellman-Ford, and it can also detect negative cycles.