Dijkstra as a Greedy Algorithm, in depth: the exchange proof, the one-line difference from Prim, and monotone bucket queues

Why the greedy choice is safe

A greedy algorithm needs two things to be correct. The greedy-choice property says some optimal solution agrees with the locally best choice. Optimal substructure says that what remains after the choice is a smaller instance of the same problem. For shortest paths, substructure is classic: every prefix of a shortest path is itself a shortest path, so shortest paths from s form a tree. The greedy choice is the subtle part.

Let S be the set of settled vertices, each with its true distance d[v]. For every vertex outside S, the tentative label is the best distance using only settled vertices as intermediates: min over x in S of d[x] + w(x, v). Let u be the outside vertex with the smallest label. Claim: the label of u is its true distance. Take any path from s to u. It starts inside S and ends outside, so it crosses the boundary for the first time at some edge (x, y), where x is in S and y is not. The part up to y costs at least d[x] + w(x, y), which is at least y's label, which is at least u's label by the choice of u. The remainder from y to u has non-negative weight. So no path beats u's label, and settling u is safe.

The proof uses non-negativity exactly once, for the remainder of the path, and that is the precise failure point. Put a negative edge in the remainder and the detour can come back cheaper than the label the greedy step committed to.

Where greed fails: negative edges

Concretely, take edges s to a with weight 2, s to b with weight 3, and b to a with weight -2. The greedy step settles a with distance 2, because 2 is smaller than 3. Then b is settled at 3, and relaxing b to a finds 1, but a is already settled. The engine below returns 2 for a; Bellman-Ford returns the true distance, 1. Nothing crashes and nothing warns. This is the general shape of greedy failure: the commitment was locally right and globally wrong.

Algorithms that never commit are called label-correcting. Bellman-Ford and its queue-based form, SPFA, may update a vertex's distance many times and stop only when nothing changes. That handles negative edges at O(nm) worst-case cost. Dijkstra is label-setting: each vertex is settled exactly once. The speed difference is the price of the greedy guarantee.

Prim is the same algorithm with one line changed

Prim's algorithm grows a minimum spanning tree with the same loop: pop the cheapest frontier vertex, add it, and update its neighbours. The only difference is the key. Dijkstra keys a frontier vertex by d[u] + w(u, v), the length of the whole path from the root. Prim keys it by w(u, v) alone, the cost of the single edge that would attach it. Prim's correctness proof is also an exchange argument, through the cut property: the lightest edge crossing any cut belongs to some minimum spanning tree.

import heapq

def greedy_tree(adj, s, key):
    # adj[u] = [(v, w), ...]. key(label_of_u, w) = priority of reaching v via u.
    best, parent, done = {s: 0}, {s: None}, set()
    pq = [(0, s)]
    while pq:
        k, u = heapq.heappop(pq)
        if u in done or k > best[u]:
            continue                       # stale entry: lazy deletion
        done.add(u)                        # the greedy commitment
        for v, w in adj[u]:
            if v in done:
                continue
            nk = key(k, w)
            if v not in best or nk < best[v]:
                best[v], parent[v] = nk, u
                heapq.heappush(pq, (nk, v))
    return best, parent

dijkstra = lambda adj, s: greedy_tree(adj, s, lambda d, w: d + w)  # path length
prim     = lambda adj, s: greedy_tree(adj, s, lambda d, w: w)      # edge weight

The engine was checked against Bellman-Ford on 300 random graphs with non-negative integer weights, and Prim's total tree weight was checked against Kruskal on 200 random connected graphs. Note what best means in each case: for Dijkstra it holds distances, and for Prim it holds the weight of the edge that attached each vertex.

Worked example: one graph, two trees

Take a square of vertices S, A, B, C with undirected edges S-A = 2, A-B = 2, B-C = 2 and a direct edge S-C = 5. Run both from S.

Dijkstra pops S (0), then pushes A at 2 and C at 5. It pops A (2) and pushes B at 4. It pops B (4); the route to C through B would cost 6, which does not beat 5. Finally it pops C at 5. The tree is S-A, A-B, S-C with total edge weight 9, and every vertex has its shortest distance: A = 2, B = 4, C = 5.

Prim pops S, pushes A and C with keys 2 and 5, pops A, pushes B with key 2, then pops B. Now C can attach through B-C with key 2, which beats 5, so C is attached by B-C. The tree is S-A, A-B, B-C with total weight 6, the minimum possible, but the tree path from S to C now costs 6 rather than 5. Neither tree is better in general; they answer different questions. A shortest-path tree is the right structure for routing from one source, and a spanning tree for connecting everything as cheaply as possible.

Monotone order and bucket queues

The greedy order has a property that turns out to be valuable: the labels that Dijkstra settles come out in non-decreasing order. With non-negative weights, every new label pushed is at least the label just popped. A priority queue that only needs to support this pattern is a monotone priority queue, and monotone queues can be much faster than general heaps when weights are integers.

Dial's algorithm uses an array of buckets indexed by distance. With maximum edge weight C, all tentative labels lie within C of the current minimum, so C + 1 buckets used circularly suffice, and the scan pointer only moves forward. The total cost is O(m + nC), which beats a binary heap when C is small, such as hop counts or small integer costs. The radix heap of Ahuja, Mehlhorn, Orlin and Tarjan uses buckets of exponentially growing width and reaches O(m + n log C).

def dial(adj, s, C):
    # Integer weights in [0, C]. Returns the distance list.
    INF = float("inf")
    dist = [INF] * len(adj)
    dist[s] = 0
    buckets = [[] for _ in range(C + 1)]      # circular: labels span at most C
    buckets[0].append(s)
    pending, cur = 1, 0
    while pending:
        b = buckets[cur % (C + 1)]
        while b:
            u = b.pop()
            pending -= 1
            if dist[u] != cur:
                continue                       # stale copy, settled earlier
            for v, w in adj[u]:
                if cur + w < dist[v]:
                    dist[v] = cur + w
                    buckets[(cur + w) % (C + 1)].append(v)
                    pending += 1
        cur += 1
    return dist

This version agreed with Bellman-Ford on the same 300 random graphs, including zero-weight edges, which land in the bucket currently being drained and are handled by the inner loop. Note the precondition: if C is large, say weights in milliseconds on a road network, the bucket scan dominates and a binary heap wins.

Relaxing the greed: delta-stepping and beyond

Strict greediness is also what makes Dijkstra hard to parallelize: one vertex is settled at a time. Delta-stepping (Meyer and Sanders) relaxes the greed. It groups labels into buckets of width delta and processes a whole bucket in parallel, re-relaxing within the bucket as needed. With delta tending to zero it becomes Dijkstra; with delta at infinity it becomes Bellman-Ford. The width tunes the trade between wasted work and parallelism.

On the theory side, the greedy order forces Dijkstra to sort vertices by distance, which suggested an O(m + n log n) "sorting barrier" for comparison-based algorithms. In 2025, Duan, Mao, Mao, Shu and Yin gave a deterministic O(m log^(2/3) n) algorithm for directed graphs with real non-negative weights in the comparison-addition model (arXiv:2504.17033). It beats Dijkstra's bound on sparse graphs by computing distances without fully ordering the vertices. It is a theoretical result; for production routing, a well-tuned Dijkstra with a good heap is still the baseline to beat.

Operational guidance

• Validate preconditions at load time: reject negative weights explicitly instead of trusting callers, because the greedy failure is silent.
• Choose the queue from the weight profile: a binary heap with lazy deletion by default, Dial for small integer weights, and a radix heap for bounded integers. The indexed heap article covers the decrease-key alternative.
• Stop early when you need only one target: once the target is popped, its label is final, which is the greedy guarantee doing useful work.
• Test against a label-correcting oracle (Bellman-Ford) on random small graphs, as above, including zero weights, self-loops and unreachable vertices.
• Name the tree you want. If callers need cheap connectivity, they need Prim or Kruskal, not a shortest-path tree.

Failure modes

• Silent negative weights. A cost derived from a difference, such as elevation change or a refund, turns negative for a few edges, and the greedy step commits too early with no error.
• Settling on push. Marking a vertex done when it is first pushed rather than when it is popped breaks the exchange argument; the first label found is not necessarily the smallest.
• Stale entries treated as live. With lazy deletion, a vertex appears in the heap several times. Forgetting the k > best[u] or done check relaxes from out-of-date labels and wastes work.
• Wrong key for the question. Using Prim's key when callers expect distances, or the reverse, returns a valid-looking tree that answers a different question, as the worked example shows.
• Dial with a large C. Real-valued or large weights make the bucket array huge and mostly empty; scale or fall back to a heap.

Trade-offs

What to do next

1. Run greedy_tree on the square example and confirm Dijkstra's tree weight is 9 and Prim's is 6.
2. Reproduce the negative-edge counterexample and write a load-time check that rejects it.
3. Implement Dial's algorithm on a grid with weights 1 to 9 and time it against heapq as C grows.
4. Write the exchange proof for Prim in the same cut form, and identify the one hypothesis that plays the role of non-negativity.
5. Read delta-stepping and decide what delta would suit your graph's weight distribution.