Dijkstra and the Settled-Set Invariant

The greedy step in Dijkstra’s algorithm looks like a leap of faith: take the vertex with the smallest tentative distance, declare its label final, and never look at it again. Nothing in the relaxation primitive from Relaxation and the Optimality Condition justifies that declaration. The justification is a separate argument, and it depends on a property of the weights rather than of the graph.

The claim and the argument

Maintain a set $S$ of settled vertices, initially empty, and tentative labels $d$ as before. Each iteration extracts $u \notin S$ minimising $d[u]$, adds it to $S$, and relaxes every outgoing edge of $u$.

The invariant is that every vertex in $S$ carries its true distance: for all $u \in S$, $d[u] = \delta(s,u)$. It is preserved by the following argument, which is an exchange argument on paths rather than on vertices.

Assume all weights are nonnegative, and suppose the algorithm is about to settle $u$, the minimum-label vertex outside $S$. Suppose, for contradiction, that $d[u] > \delta(s,u)$. Consider a genuine shortest path $p$ from $s$ to $u$. Since $s \in S$ and $u \notin S$, the path leaves $S$ at some point; let $y$ be the first vertex on $p$ that lies outside $S$, and let $x \in S$ be its predecessor on $p$. Because $x$ was settled, its outgoing edges were relaxed, so

$$d[y] \le d[x] + w(x,y) = \delta(s,x) + w(x,y) = \delta(s,y),$$

where the last equality uses the fact that a prefix of a shortest path is shortest. Since $y$ lies on a shortest path to $u$, $\delta(s,y) \le \delta(s,u)$, because the remainder of the path from $y$ to $u$ has nonnegative weight. Chaining the inequalities gives

$$d[y] \le \delta(s,y) \le \delta(s,u) < d[u].$$

But $u$ was chosen as the minimum-label vertex outside $S$, and $y$ is outside $S$ with a strictly smaller label. That is a contradiction, so $d[u] = \delta(s,u)$.

The step $\delta(s,y) \le \delta(s,u)$ is exactly where nonnegative weights enter. If the tail of the path could have negative total weight, $y$ could be farther from $s$ than $u$ is, the chain breaks, and the contradiction evaporates. Every other part of the argument holds for arbitrary weights, which is why the failure of Dijkstra on negative edges is a failure of one inequality rather than of the greedy idea in general.

What the settled set buys and costs

Settling a vertex converts a tentative label into a permanent one. That has three consequences.

The first is termination and a bound on work: each vertex leaves the queue once, so each edge is relaxed exactly once, from its tail. The total number of relaxation calls is $|E|$, not $|E|$ times some number of rounds. This is the entire performance advantage over the round-based method described in Bellman-Ford, Round Counts, and Negative-Cycle Detection: the same primitive, applied once per edge instead of $|V|-1$ times per edge.

The second is a memory cost of one bit or one byte per vertex for membership, plus whatever the priority queue needs. For a graph with a billion edges this is not free, but it is small relative to the adjacency structure itself.

The third is that the algorithm cannot revisit a decision. A vertex that has been settled and later found to have a cheaper route is a correctness bug, not a recoverable state. Implementations that check for this, by comparing a newly computed candidate against a settled label, are detecting violated preconditions, most often negative weights or integer overflow.

A counterexample worth remembering

Three vertices: $s \to a$ with weight 1, $s \to b$ with weight 2, $b \to a$ with weight $-2$. The algorithm settles $a$ first with $d[a] = 1$, then settles $b$ with $d[b] = 2$, then relaxes $b \to a$ and computes $d[b] + w(b,a) = 0 < 1$. The true distance to $a$ is 0, and $a$ has already been finalised.

Note what the counterexample is not: it is not a negative cycle. The graph is acyclic and every distance is well defined. Nonnegative weights are a sufficient condition for the greedy step, not a necessary one, so the precondition belongs to the input rather than to the code. The practical rule is to reject negative weights at the API boundary rather than to hope.

The queue is the algorithm’s cost

The complexity statement usually quoted is $O((|V| + |E|) \log |V|)$, which assumes a binary heap with $|V|$ extractions and up to $|E|$ decrease-key operations. It is worth being precise about which operations the bound charges for, because the variant that avoids decrease-key entirely has a different and often better constant.

With a binary heap and decrease-key, each relaxation that improves a label triggers a sift-up costing $O(\log |V|)$, so the worst case is dominated by $|E|$ logarithmic operations. With a lazy heap that pushes a duplicate entry on every improvement and discards stale entries at extraction time, there are up to $|E|$ pushes instead of $|V|$ pushes plus decrease-keys, so the heap can hold $O(|E|)$ entries and the bound becomes $O(|E| \log |E|)$, asymptotically worse by a factor that depends on the edge-to-vertex ratio, but usually faster in practice because a sift-up is cheaper than locating and decreasing a key. Priority Queues and Decrease-Key in Dijkstra compares the alternatives in detail.

The array-based variant, which scans all unsettled vertices for the minimum each iteration, costs $O(|V|^2 + |E|)$ and needs no heap at all. On dense graphs, where $|E|$ is on the order of $|V|^2$, it is competitive with the heap version and has a far smaller constant and footprint. That trade, with dense graphs favouring scanning and sparse graphs favouring heaps, is the oldest structural decision in the algorithm’s implementations.

Ties, integer weights, and early exit

Three details change behaviour without changing correctness.

Equal labels can be extracted in any order. When several vertices share the minimum label, the choice of which to settle first can change the shape of the resulting shortest-path tree, and therefore which of several equal-cost routes gets reported. If a caller needs deterministic output, the comparison must break ties on a stable key such as vertex index; heap implementations that compare only labels will produce output that varies with insertion order.

Integer weights allow a monotone bucket queue instead of a comparison heap. When weights are small nonnegative integers bounded by $C$, labels fall into a bounded range and can be processed in first-in-first-out buckets indexed by distance, which gives $O(|E| + |V| \cdot C)$ time with no logarithmic factor at all. The technique is usually attributed to Dial, and it degrades badly when $C$ is large, because the number of buckets and the scanning work grow with the weight range rather than with the graph size. Mixed weights, with some integer and some floating point, rule it out.

Early exit is valid when only one destination matters. Once the target vertex is extracted, its label is final and the search can stop, which typically settles a small fraction of the graph. This is a legitimate optimisation because it uses the invariant rather than bypassing it; stopping before the target is extracted, or stopping when the target’s label is merely finite, is not.

Where it stops being the right tool

Dijkstra answers one source, one direction, nonnegative weights. It says nothing about negative weights, nothing about all pairs, and its exploration is undirected by the goal: the frontier expands as a roughly circular region around the source regardless of where the destination lies. Adding a heuristic that estimates the remaining distance reshapes that region and is the subject of A* and the Conditions on a Heuristic.

On continent-scale road networks even the reshaped version explores far more of the graph than the geometry suggests it should, and the methods that fix that do so by preprocessing the graph rather than by improving the search, as described in Contraction Hierarchies and Preprocessing for Road Networks.