Dijkstra's Algorithm, in depth: the settled-frontier invariant, a correct implementation, negative edges and production pitfalls

The one idea: grow a settled region outward

Imagine pouring water in at the source and letting it flow along edges at constant speed, where an edge of weight 5 takes 5 time units to cross. Nodes get wet in order of their distance from the source. Dijkstra's algorithm simulates this: at every step it takes the nearest node that is not yet final and declares its distance final.

Formally, the algorithm keeps three groups of nodes. Settled nodes have a final distance. Frontier nodes have been reached by at least one edge from a settled node and carry a tentative distance, the best found so far. Unreached nodes have distance infinity. Each iteration removes the frontier node with the smallest tentative distance, settles it, and relaxes each outgoing edge: if going through u gives v a shorter distance than v currently has, update v and put it on the frontier.

The invariant that makes this work: when the minimum frontier node is popped, its tentative distance is already the true shortest distance. That claim depends on every edge weight being non-negative, and nothing else in the algorithm does.

A correct implementation in Python

The version below uses Python's heapq, a binary heap with no decrease-key operation. Instead of updating a node's priority in place, it pushes a new entry and leaves the old one in the heap. When the old, larger entry is eventually popped, the check d > dist[u] recognises it as stale and skips it. This is called lazy deletion, and it is what most production code does, because it is simpler and usually faster than maintaining heap handles. The heap operations article explains why decrease-key needs a position index and what that index costs.

import heapq
from math import inf

def dijkstra(graph, source, target=None):
    """graph: {u: [(v, w), ...]} with every w >= 0. Returns (dist, parent)."""
    dist = {source: 0}
    parent = {source: None}
    pq = [(0, source)]                     # (tentative distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:                    # stale entry: u was improved after this push
            continue
        if u == target:                    # early exit: target is settled, d is final
            break
        for v, w in graph.get(u, ()):
            nd = d + w
            if nd < dist.get(v, inf):      # relaxation
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent

def path_to(parent, target):
    if target not in parent:
        return None                        # unreachable
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

g = {"A": [("B", 4), ("C", 2)],
     "C": [("B", 1), ("D", 8), ("E", 10)],
     "B": [("D", 5)],
     "D": [("E", 2), ("F", 6)],
     "E": [("F", 2)]}
dist, parent = dijkstra(g, "A")
print(dist)                  # {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 12}
print(path_to(parent, "F"))  # ['A', 'C', 'B', 'D', 'E', 'F']

Three details matter. The stale check compares against the current best distance, so a node can be pushed several times but is expanded once with its final distance. The parent map records the edge that produced each improvement, so the shortest path tree comes out for free and a path is recovered by walking parents back from the target. And the early exit on u == target is safe only after the pop, because a node's distance is final when it is popped, not when it is first pushed.

Worked example: tracing the six-node graph

Run the code above from A. The table lists every pop in order, what happened, and the pushes it caused. It was produced by running the function, not by hand, so you can reproduce it line for line.

Notice that the direct edge A to B (weight 4) was beaten by the two-hop route A, C, B (2 + 1 = 3). Greedy choices on single edges are wrong; greedy choices on whole distances are right. Also notice the four stale pops: the heap holds one entry per successful relaxation, so its size is bounded by E rather than V.

Why it is correct

The proof is an exchange argument of the kind described in the greedy algorithms article. Suppose u is the frontier node with the smallest tentative distance d[u], and suppose some path P from the source to u is shorter than d[u]. P starts inside the settled set and ends at u outside it, so it has a first edge (x, y) that leaves the settled set. Because x is settled, that edge was relaxed when x was settled, so d[y] is at most the length of P up to y.

Now the step that needs non-negative weights: the rest of P, from y to u, has length at least zero, so the length of P up to y is at most the length of all of P, which by assumption is less than d[u]. That gives d[y] less than d[u], contradicting the choice of u as the minimum. Therefore no shorter path exists and d[u] is final.

If an edge on the y-to-u tail could be negative, the tail could make P shorter than its prefix and the proof falls apart: a node can be popped before a cheaper route through a negative edge is discovered.

Negative edges: what actually happens

Tutorials often say Dijkstra "fails" with negative edges. The truth depends on which variant you wrote. The settle-once variant, which marks a node done at its first pop and never touches it again, does return wrong answers. The lazy-deletion loop above does not mark nodes done; if a later relaxation lowers a popped node's distance it gets pushed and expanded again. On graphs with negative edges and no negative cycles it therefore returns correct distances, but the running time bound is gone: there are graphs where the number of re-expansions grows exponentially with the node count. With a negative cycle it never terminates, because the cycle keeps lowering distances forever.

# A "settle once" variant: common in textbooks, fine for w >= 0, wrong for w < 0.
def dijkstra_settle_once(graph, source):
    dist, done, pq = {source: 0}, set(), [(0, source)]
    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, inf):
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    return dist

neg = {"A": [("B", 2), ("C", 3)], "C": [("B", -2)], "B": [("D", 1)]}
print(dijkstra_settle_once(neg, "A"))  # B=2, D=3  (wrong: true B=1, D=2)
print(dijkstra(neg, "A")[0])           # B=1, D=2  (right, but B is settled twice)

The practical rule stays the same: do not feed negative weights to Dijkstra. If they are possible, use Bellman-Ford, which runs in O(VE), tolerates negative edges and detects negative cycles. For many queries on such a graph, Johnson's technique runs Bellman-Ford once to compute potentials, reweights edges to be non-negative, then runs Dijkstra. Either way, validate weights at load time and fail loudly.

Priority queue choices and what they cost

Dijkstra performs V pops and up to E relaxations. The data structure behind the frontier decides what those operations cost.

Measure before switching. On large sparse graphs a binary or 4-ary heap over contiguous arrays typically beats pointer-based heaps with better asymptotics, because memory access dominates. On dense graphs the array scan does less work than any heap.

An engineering version: int arrays in Java

Object-per-node graphs and a heap of boxed pairs spend most of their time in allocation and pointer chasing. The version below stores the graph in compressed sparse row form: edges of node u occupy positions head[u] to head[u+1] - 1 of the to and wt arrays. Distances are long, so summing many large int weights cannot overflow and wrap to a negative number, a bug that silently corrupts the ordering.

// Compressed sparse row graph: edges of u are head[u] .. head[u+1]-1 in to[] / wt[].
static long[] dijkstra(int n, int[] head, int[] to, int[] wt, int src, int[] parent) {
    long[] dist = new long[n];
    java.util.Arrays.fill(dist, Long.MAX_VALUE);
    java.util.Arrays.fill(parent, -1);
    dist[src] = 0;
    // Pack (distance, node) into one long so the heap holds primitives, not objects.
    // Valid while distances stay below 2^(63 - 20) and n is below 2^20; check both up front.
    java.util.PriorityQueue<Long> pq = new java.util.PriorityQueue<>();
    pq.add(0L << 20 | src);
    while (!pq.isEmpty()) {
        long top = pq.poll();
        int u = (int) (top & 0xFFFFF);
        long d = top >>> 20;
        if (d > dist[u]) continue;                   // stale
        for (int e = head[u]; e < head[u + 1]; e++) {
            int v = to[e];
            long nd = d + wt[e];                     // long: no int overflow on sums
            if (nd < dist[v]) {
                dist[v] = nd;
                parent[v] = u;
                pq.add(nd << 20 | v);
            }
        }
    }
    return dist;
}

Packing distance and node id into one long is a common trick to keep the heap entries comparable without objects, but it imposes limits: here node ids must fit in 20 bits and distances in the remaining 43. Assert both at load time. PriorityQueue<Long> still boxes; a hand-written heap over a long[] removes that.

Variants and when to use something else

• Unweighted graphs: plain BFS gives shortest paths in O(V + E); the heap is wasted work.
• Weights of 0 or 1: 0-1 BFS uses a deque, pushing 0-edges to the front and 1-edges to the back, for O(V + E).
• One target with a good distance estimate: A* is Dijkstra with priority d[v] + h(v). With a consistent heuristic it settles fewer nodes and stays correct; with h = 0 it is exactly Dijkstra.
• Point-to-point on huge static graphs: bidirectional search from both ends roughly halves the explored radius; road routing engines go further with preprocessing such as contraction hierarchies, trading hours of preprocessing for millisecond queries.
• Several sources at once: push every source with distance 0 before the loop. The result is the distance to the nearest source, for example the nearest hospital from every intersection.

Failure modes in real code

• Settling on push instead of pop. Marking a node final when it is first discovered returns the first route found, not the shortest one.
• Early exit before the pop. Returning when the target is first relaxed has the same bug in a less visible place.
• Integer overflow. Using INT_MAX as infinity and then adding a weight wraps negative; the node now looks closest of all. Use a wider type or guard the addition.
• Floating-point weights. Sums of floats are not associative, so equal-cost paths can compare unequal and tests that assert a specific path become flaky. Compare with a tolerance or use integers in fixed units.
• Unreachable nodes. Code that reads dist[target] without checking for infinity reports a huge number as a cost, or crashes reconstructing a path with no parent chain.
• Negative weights slipping in. A cost model that subtracts a discount or a reward can produce negative edges long after the graph code was written. Validate at load time.

What to do next

1. Type in the Python version, run it on the six-node graph and check that your output matches the trace table, including the four stale pops.
2. Run both variants on the negative-edge graph and confirm the settle-once version returns B = 2 while the lazy version returns B = 1.
3. Add a load-time check that rejects negative weights, and a test for an unreachable target.
4. Write a brute-force checker for small graphs (Bellman-Ford or enumerating paths) and compare it with your Dijkstra on thousands of random graphs.
5. Benchmark lazy deletion against the array-scan version on a sparse and a dense random graph of the same node count and note where they cross.