Dijkstra's Invariant

The single-source shortest path

Given a directed graph with non-negative edge weights and a source node, compute the shortest distance from the source to every other node. BFS handles the unweighted case in O(V + E). With weights, BFS no longer works because closer-in-edges is no longer the same as closer-in-weight. Dijkstra's algorithm generalises BFS to weighted graphs.

Implementation

import heapq

def dijkstra(graph, source):
    dist = {source: 0}
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue                                    # stale entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

The key line is if d > dist.get(u, float('inf')): continue, the lazy-deletion trick. We never bother to remove stale entries from the heap; we just skip them on pop.

The invariant, proved

Claim: when Dijkstra pops node u with distance d, the value d is the true shortest distance from source to u.

Proof. Suppose not: there is a shorter path P from source to u. P goes from source through some sequence of nodes to u. Consider the first node x on P that has not yet been popped from the queue. (At least one exists: u itself.)

The node y just before x on P has been popped (by choice of x). When y was popped, the algorithm relaxed the edge from y to x, which set dist[x] to (at most) dist[y] + weight(y, x). Since the weights are non-negative, this is at most the total weight of P (which is < d).

So dist[x] < d when x sits in the queue. But x has not yet been popped, which means x's queue entry has a smaller priority than d. The heap would have popped x before u. Contradiction. Therefore no shorter path P exists.

The proof relies on "weights are non-negative." A negative edge later in P could allow the total weight of P to be less than dist[y] + weight(y, x), breaking the conclusion. That's precisely why Dijkstra fails on negative weights.

Lazy deletion: why it's correct

When we discover a shorter path to v, we push a new (distance, v) onto the heap. The old (older-distance, v) is still there. When we pop, we get the smallest distance first. If we see (older-distance, v) at any point, its distance must be at least as large as the value already in dist[v], so we skip it.

The total number of heap operations is bounded by E (one push per edge relaxation) plus V (one push per source initialisation). Each is O(log heap-size) = O(log E) = O(log V). Total: O((V + E) log V).

Eager deletion (decrease-key) is theoretically faster (Fibonacci heaps achieve O(V log V + E)), but the constant factors are awful. Binary heap with lazy deletion wins on real workloads.

A worked trace

Graph: A → B (weight 1), A → C (weight 4), B → C (weight 2), B → D (weight 5), C → D (weight 1).

start: dist = {A: 0}, pq = [(0, A)]

pop (0, A): relax B (set dist[B]=1, push), relax C (set dist[C]=4, push)
            pq = [(1, B), (4, C)]

pop (1, B): relax C (1 + 2 = 3 < 4 → set dist[C]=3, push), relax D (1 + 5 = 6, push)
            pq = [(3, C), (4, C), (6, D)]

pop (3, C): relax D (3 + 1 = 4 < 6 → set dist[D]=4, push)
            pq = [(4, C), (4, D), (6, D)]

pop (4, C): d=4, dist[C]=3, so d > dist[C] → skip (lazy deletion)

pop (4, D): no outgoing edges (or all relaxations fail) → done

pop (6, D): d=6, dist[D]=4, so d > dist[D] → skip

final: dist = {A: 0, B: 1, C: 3, D: 4}

Notice the two skipped pops: the lazy-deletion check fires on (4, C) and (6, D), both stale entries. The total useful pops equals V; the total pops including stale ones is bounded by E + V.

Sparse vs dense graphs

For sparse graphs (E ≈ V), Dijkstra with a binary heap is O((V + E) log V) ≈ O(V log V). For dense graphs (E ≈ V²), the same algorithm is O(V² log V), and a simpler array-based Dijkstra (scan all V nodes to find the minimum each round) achieves O(V²), strictly better.

Pick the implementation by the graph's density. Most interview problems are sparse, so the heap version is usually the right choice.

When Dijkstra fails: Bellman-Ford

Negative edge weights break Dijkstra. The simplest counter-example: source A, A → B with weight 5, A → C with weight 1, C → B with weight −10. Dijkstra pops A, then C (distance 1), then B (distance 5). But the true shortest path is A → C → B with weight −9.

Bellman-Ford handles negative weights by relaxing every edge V − 1 times. Each pass guarantees that one more "level" of optimal distances is finalised. Time: O(V × E). Memory: O(V). Slower than Dijkstra but correct on negatives.

Bellman-Ford also detects negative cycles (run one more pass; if anything changes, there's a negative cycle reachable from the source).

Extensions

• A* search: Dijkstra with a heuristic added to the priority. priority = distance + h(node). Reduces to Dijkstra when h ≡ 0; faster than Dijkstra when h is admissible (never overestimates) and informative.
• K-shortest paths: Dijkstra-like, but allow each node to be "finalised" up to K times. Yen's algorithm for the deviation form.
• Multi-source Dijkstra: initialise dist[s] = 0 for every source s, push all sources to the queue. Computes the shortest distance from any source to each node, useful in "nearest hospital" problems.

Where beginners go wrong

• Skipping the lazy-deletion check. Without it, the algorithm processes the same node multiple times. Same answer, but with E × log E redundant work.
• Applying Dijkstra to a graph with negative weights. Wrong answers, silently. Always check the weight constraints before reaching for Dijkstra.
• Storing (node, dist) instead of (dist, node). Python's heap compares tuples element-wise. The first element must be the priority. Reversing them silently breaks the heap order.
• Trying to decrease-key manually. Lazy deletion handles this for you; reaching into the heap for a specific entry breaks the heap invariant.
• Forgetting to track dist separately from the heap. The heap holds tentative distances; dist holds the best known so far. The lazy-deletion check compares the popped tentative against dist.

What to read next

The BFS vs DFS deep-dive covers the unweighted parents of Dijkstra. The Graphs module covers Bellman-Ford, Floyd-Warshall, and other shortest-path algorithms. Heap as Array Arithmetic explains the priority queue Dijkstra depends on.