Dial's Algorithm, in depth: bucket queues for small integer weights, the circular array, lazy deletion and when it beats a heap

The idea: a priority queue indexed by distance

Dijkstra's invariant is that vertices are settled in non-decreasing order of distance. The queue only has to answer one question: what is the smallest tentative distance not yet settled? If distances are integers, imagine an array B where B[k] holds every vertex whose tentative distance is k. Start with the source in B[0]. Keep a cursor d at the current distance. Repeatedly take any vertex from B[d]; if B[d] is empty, advance d. When you settle a vertex u at distance d and relax an edge (u, v, w), put v into B[d + w] if that improves it.

Because the cursor only moves forward and every new label is at least d (weights are non-negative), the cursor never needs to look back. This is a monotone priority queue: the extracted minimum never decreases, and Dial's algorithm is the simplest structure that exploits it. The cursor walks at most from 0 to the largest finite distance D, so the total scanning work is O(D), on top of O(1) per edge relaxation.

Why C + 1 buckets in a circle are enough

A naive array needs D + 1 buckets, and D can be as large as (n - 1)C. The fix is the key observation of the algorithm. When the cursor is at d, every vertex still waiting in the queue has a label in the closed range [d, d + C]. The lower end holds because labels below d would already have been settled. The upper end holds because each label was created as d' + w for some settled distance d' at most d and some weight w at most C.

A range of C + 1 consecutive integers has C + 1 distinct residues modulo C + 1. So an array of exactly C + 1 buckets, indexed by label mod (C + 1), never puts two different live distances in the same bucket. Memory drops from O(nC) to O(C) buckets plus O(m) entries.

Decrease-key is avoided with lazy deletion. When a vertex's label improves, append it to its new bucket and leave the old entry where it is. When an entry is popped, compare the bucket's distance with the vertex's current label; if they differ the entry is stale and is skipped. Each successful relaxation adds one entry, so there are at most m stale entries.

The algorithm in code

The implementation below is complete. It was checked against a binary-heap Dijkstra on 500 random directed graphs with up to 60 vertices, weights from 0 to C and C up to 12, including zero-weight edges and self-loops; the distance arrays matched in every case.

def dial(n, adj, src, C):
    """Single-source shortest paths for integer weights in [0, C].
    adj[u] is a list of (v, w). Returns (dist, parent)."""
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n
    dist[src] = 0
    B = C + 1                          # live labels always fit in [d, d + C]
    buckets = [[] for _ in range(B)]
    buckets[0].append(src)
    pending = 1                        # entries in buckets, stale ones included
    d = 0                              # cursor: the distance being settled
    while pending:
        bucket = buckets[d % B]
        while not bucket:              # advance to the next non-empty bucket
            d += 1
            bucket = buckets[d % B]
        u = bucket.pop()
        pending -= 1
        if dist[u] != d:               # lazy deletion: an older, worse label
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                parent[v] = u
                buckets[nd % B].append(v)   # w == 0 lands in the current bucket
                pending += 1
    return dist, parent

Three details matter. The pending counter, not a scan of all buckets, decides termination, so the loop stops as soon as the last entry is consumed. Zero-weight edges are safe because they append to the bucket currently being drained, and the outer loop pops from it again before advancing. And the stale check uses equality with d: a stale entry always carries a label larger than the vertex's final distance, so the vertex was settled earlier and dist[u] is now smaller than d.

Using pop() makes each bucket a stack. Order inside a bucket does not affect correctness because every vertex in it has the same distance, but it does affect which shortest path the parent array records when there are ties. If you need deterministic tie-breaking, for example to make route outputs reproducible across runs, use a deque and document the rule.

Worked example: six vertices, five buckets

Take the graph in the figure with source s and C = 4, so there are five buckets. Settling s at d = 0 puts a into bucket 2 (label 2) and b into bucket 4 (label 4). The cursor advances to 2 and settles a, which improves b to 3 (bucket 3) and gives c the label 6. Six mod 5 is 1, so c goes into bucket 1, behind the cursor in array order but ahead of it in distance. That wrap-around is exactly what the [d, d + C] argument licenses.

At d = 3 the cursor settles b. It improves c to 5 (bucket 0) and gives d the label 6 (bucket 1). At d = 4 the cursor finds the stale entry for b, whose label is now 3, and skips it. At d = 5 it settles c from bucket 0; relaxing c to t gives 8 (bucket 3), and c to d gives 6, which is not an improvement. At d = 6 bucket 1 holds d and the stale c; d settles and the stale c is skipped. Bucket 2 at d = 7 is empty, and t settles at d = 8. Final distances: s 0, a 2, b 3, c 5, d 6, t 8. The cursor made eight empty-bucket advances and handled two stale entries, against nine relaxations.

What it costs, and what the bound hides

Every edge is relaxed once, when its tail is settled: O(m). Every entry is pushed and popped once: O(m). The cursor moves from 0 to D, the largest finite distance: O(D), which is at most O(nC). The total is O(m + D), usually quoted as O(m + nC). Space is O(n + m + C).

Compare that with O((n + m) log n) for a binary heap. Dial wins when C is small relative to m log n divided by n. On a road grid with a million vertices and weights 1 to 10, nC is ten million cursor steps of a tight loop, comparable to the m log n of about 80 million heap comparisons with cache misses. With weights up to a million, the same graph would make the cursor walk up to a trillion empty buckets, and the algorithm is hopeless.

The bound hides two things. First, D is often much smaller than nC: distances are bounded by the shortest path, not the longest, so measured cursor work is frequently a small multiple of n. Second, the constant per operation is tiny: an array append and pop with no comparisons, which is friendly to branch predictors. Empirical studies of shortest-path codes, notably Cherkassky, Goldberg and Radzik (1996), found bucket-based implementations among the fastest in practice on many graph families.

Relatives: 0-1 BFS, radix heaps, multi-level buckets, delta-stepping

Several structures generalise the bucket idea. Choose by what breaks first: weight range, memory, or parallelism.

• 0-1 BFS is Dial with C = 1, where two buckets collapse into a deque: push zero-weight neighbours to the front and unit-weight ones to the back. See 0-1 BFS in depth.
• Multi-level buckets (Denardo and Fox, 1979) use a coarse array of wide buckets and expand only the current one into fine buckets, cutting cursor work when C is large.
• Radix heaps (Ahuja, Mehlhorn, Orlin and Tarjan, 1990) use buckets of exponentially growing width relative to the last extracted key, giving O(m + n log C) with integer keys. They are the usual answer when C is too big for Dial but keys are still integers.
• Delta-stepping (Meyer and Sanders) uses buckets of width delta and relaxes all vertices in a bucket in parallel, separating light from heavy edges. It is the standard parallel single-source shortest-path algorithm, and Dial is its sequential delta = 1 case.
• Heaps remain the general answer for real-valued weights. See Dijkstra in depth for the invariant and Dijkstra with a Fibonacci heap for the asymptotic extreme.

Failure modes

• Non-integer weights. Floats break the bucket index. Scale to integers only if the rounding error is acceptable: multiplying by 100 and rounding can reorder near-tied paths, and the scaled C grows by the same factor.
• A weight larger than C. One edge above the declared bound puts a label outside [d, d + C], it lands in a bucket that is read too early, and distances are silently wrong. Compute C from the data at build time and assert every weight is within range.
• Negative weights. The cursor never moves back, so a negative edge produces wrong answers without an error. Validate inputs, or use Bellman-Ford or Johnson's reweighting.
• Huge C with sparse graphs. The cursor spins through empty buckets. Monitor the ratio of empty advances to settled vertices; if it is above ten or so, switch to a radix heap or multi-level buckets.
• Termination by scanning. Stopping when a full lap of C + 1 buckets is empty works, but costs O(C) per query at the end; a pending counter is cheaper and clearer.
• Point-to-point queries. Stop when the target is settled, not when the queue drains. Forgetting this turns a local query into a full single-source computation.

Operational guidance

In production, Dial's algorithm is usually embedded in a bigger system: a router computing paths over link costs, a game server pathfinding on a weighted grid, or a timetable engine running many queries per second. A few habits keep it fast and correct.

1. Store the graph in compressed sparse row form (offset array plus edge arrays) so relaxation is a linear scan. This matters more than the queue for large graphs.
2. Reuse the distance and bucket arrays between queries and reset only the vertices you touched, kept in a list. Clearing an n-sized array per query dominates short queries.
3. Instrument settled vertices, stale pops and empty advances per query. Stale pops above about half of pushes suggest many improvements per vertex; empty advances far above n suggest C is too large for this structure.
4. Benchmark against a binary heap with lazy deletion on your real graphs and weights, at your real query mix. If the heap is within 20 percent, keep the heap: it handles any future weight change without an invariant to break.
5. For link-state routing, note that OSPF's SPF calculation uses 16-bit interface costs, so C can reach 65,535; whether buckets pay off depends on the cost plan, not the protocol.

Trade-offs

What to do next

1. Measure the actual weight range of your graph and compute C; reject the data if any weight is negative or non-integer.
2. Implement dial() above with a pending counter and lazy deletion, then fuzz it against a heap-based Dijkstra on random graphs that include zero weights.
3. Add early exit for point-to-point queries and the touched-vertex reset for repeated queries.
4. Instrument empty advances and stale pops, and run both queues on your production graph and query mix.
5. If C turns out to be large, try a radix heap before giving up on integer structure; if you need parallelism, read up on delta-stepping.
6. Revisit Dijkstra as a reusable engine to put the bucket queue behind the same interface as your heap, so switching is a configuration change.