Dijkstra and Why It Needs Non-Negative Weights

From patient relaxation to a greedy order

The previous guide left us with one operation, relaxation, and one promise: if we relax edges in the right order, every tentative distance eventually settles on the true shortest distance from the source. The trouble is the phrase the right order. Bellman-Ford, which the next guide covers, gives up on cleverness and just relaxes every edge over and over, paying O(V·E) for the privilege. Dijkstra's question is sharper: can we find an order so good that we relax each edge only once and never have to revisit it?

Dijkstra's answer is a greedy ordering. Keep two groups of vertices: finalized ones, whose shortest distance we have locked in, and frontier ones, which still carry a tentative distance that might improve. At every step, look across all non-finalized vertices, pick the one with the smallest tentative distance, and declare it finalized. Then relax its outgoing edges to possibly lower the tentatives of its neighbors, and repeat. The whole algorithm is just that loop: pick the closest, lock it, relax outward.

A tiny trace

Let us run it by hand on four vertices. Source s, with edges s→a of weight 1, s→b of weight 4, a→b of weight 2, and a→c of weight 5, b→c of weight 1. Start: every distance is infinity except dist(s) = 0. The frontier is {s, a, b, c} with tentatives 0, ∞, ∞, ∞. Pick the smallest — s, at 0 — finalize it, and relax its edges: a drops to 1, b drops to 4.

1. Finalized {s}. Frontier tentatives: a=1, b=4, c=∞. Smallest is a=1, so finalize a. Relax a's edges: b via a is 1+2 = 3, which beats 4, so b drops to 3; c via a is 1+5 = 6, so c drops to 6.
2. Finalized {s, a}. Frontier: b=3, c=6. Smallest is b=3, so finalize b. Relax b's edges: c via b is 3+1 = 4, which beats 6, so c drops to 4.
3. Finalized {s, a, b}. Frontier: c=4. Finalize c at 4. Nothing left to relax. Done — final distances are s=0, a=1, b=3, c=4.

Stare at the moment we finalized b at 3. There were still un-finalized vertices around (c at 6), but we committed to b without ever looking again. That commitment is the source of Dijkstra's speed — and it is exactly the gamble we now have to justify. Why are we allowed to believe that 3 is b's final answer, when more relaxations are still to come?

Why the gamble is safe — when weights are non-negative

The claim to defend is the greedy choice property: at the instant we pick the frontier vertex u with the smallest tentative distance, that tentative distance already equals u's true shortest distance. If this holds, finalizing u is never premature, and one pass suffices. The proof is a small, beautiful argument — a stays-ahead style contradiction that hinges entirely on edges never having negative weight.

Suppose, for contradiction, that u's true shortest distance is strictly less than its tentative distance d(u) at the moment we pick it. Then some genuinely shorter path P reaches u. Walk along P from the source; since the source is finalized and u is not, P must cross from the finalized set to the frontier at some edge (x, y), where x is finalized and y is the first frontier vertex on P. Because x was finalized earlier with the correct distance, and we relaxed x's edges when we finalized it, y already has a tentative value at most dist(x) + weight(x,y) — which is the length of P up to y.

Now the punchline. The length of P up to y is at most the length of all of P (because the rest of P, from y onward to u, has length ≥ 0 — this is where non-negativity is used). And all of P is, by assumption, shorter than d(u). So y's tentative value is less than d(u). But that contradicts our choosing u as the smallest frontier vertex — y was sitting right there in the frontier with a smaller value. The contradiction means no such shorter path exists: d(u) was correct all along.

One negative edge, and the house falls

Let us watch the failure happen, because nothing builds intuition like a counterexample you traced yourself. Three vertices, source s, with edges s→a of weight 1, s→b of weight 2, and b→a of weight -2 (a negative edge). The true shortest distance to a is via b: 2 + (-2) = 0, which beats the direct 1. But watch Dijkstra.

1. Finalize s at 0. Relax: a drops to 1, b drops to 2. Frontier: a=1, b=2.
2. Smallest frontier vertex is a at 1, so finalize a at 1 — and lock it forever. This is the fatal step: a is committed before b is even processed.
3. Now finalize b at 2 and relax b→a: 2 + (-2) = 0, which is less than a's stored 1. But a is already finalized; the standard algorithm never revisits it. Dijkstra reports dist(a) = 1. The true answer is 0. It is simply wrong.

This is exactly the case our proof forbade. The greedy argument assumed that once you reach a vertex, no future detour can make it cheaper, because every remaining edge adds something non-negative. A negative edge breaks that assumption: a longer-looking route through b subtracts on its way to a, so finalizing a early — while it still looked like the best — was a mistake that the algorithm has no mechanism to undo. The error is not a bug in any implementation; it is baked into the greedy strategy itself.

Making it fast: the priority queue

Correctness settled, what does Dijkstra cost? The expensive part is 'find the frontier vertex with the smallest tentative distance' — done V times. A naive scan of all vertices each time gives O(V^2), which is genuinely fine, even optimal, for dense graphs where E is close to V^2. But for sparse graphs we want better, and the tool is a min-priority-queue (a binary heap): it serves up the smallest tentative in O(log V), and supports lowering a key when relaxation improves a neighbor.

Count the heap operations. Each vertex is extracted once (V extract-min operations), and each edge can trigger at most one decrease-key (E of them). Every heap operation is O(log V), giving O((V + E) log V), usually written O(E log V) since E ≥ V on a connected graph. That is the running time you should commit to memory. With a fancier Fibonacci heap the decrease-keys become O(1) amortized and the bound improves to O(E + V log V) — a theoretical win that rarely beats a plain binary heap in practice, a small reminder that the hidden constants matter.

dist[s] = 0; all other dist = +inf
push (0, s) into min-heap PQ
while PQ not empty:
    (d, u) = extract-min(PQ)
    if d > dist[u]: continue        # stale entry, skip
    for each edge (u, v, w):
        if dist[u] + w < dist[v]:   # relaxation
            dist[v] = dist[u] + w
            push (dist[v], v) into PQ

What you walk away with

Dijkstra is the cleanest case study in this whole ladder of how a greedy choice earns its keep — and of how narrow the conditions for that earning can be. The same loop that is provably optimal on non-negative weights is provably wrong with a single negative edge, and no amount of careful coding rescues it; only a different paradigm does. When you reach for Dijkstra, the first question is never 'is the graph big?' but 'are all weights non-negative?' — and the triangle inequality from the previous guide is the quiet fact underneath both its correctness here and its failure there.

It also leaves you with a transferable habit. Whenever someone proposes a greedy algorithm, do what we did: find the single line in its correctness proof that depends on an assumption about the input, then ask what breaks when that assumption is dropped. For Dijkstra it was 'remaining path length ≥ 0.' Knowing where a proof leans is knowing exactly when an algorithm may be trusted — the whole point of building a shortest-path tree you can actually rely on.