Dial's Algorithm

Dial's Algorithm is Dijkstra's shortest-path algorithm with the priority queue swapped for a much simpler structure: an array of buckets, one per possible distance. When edge weights are small non-negative integers, this is faster and dead simple to code.

The slow way first

Plain Dijkstra uses a binary heap to always pull out the nearest unsettled vertex. Each pop and each update costs O(log n), so the total is O((V + E) log V). The log factor comes entirely from keeping a sorted-ish priority queue.

The question to ask: do I really need a general heap? If every edge weight is a small integer, the largest distance is at most (n − 1) · W, a modest number. We can index vertices directly by their distance instead of comparing them.

The idea: one bucket per distance

Keep an array buckets where buckets[d] holds every vertex whose current tentative distance is exactly d. Start the source in buckets[0]. Then sweep the bucket index d upward from 0: the lowest non-empty bucket always contains the next vertex to settle, so popping it is the heap's job done in O(1). Relaxing an edge that improves a vertex just appends it into the bucket for its new, smaller distance.

Because we never move the sweep index d backward and a vertex only ever lands in a bucket at a distance we have not passed yet, the first time we pop a vertex its distance is final. Old copies sitting in higher buckets are simply skipped.

Walk through it

Step through the animation. A starts in bucket 0 with distance 0. We pop it, relax A→B and A→C, and B, C land in buckets 1 and 3. Watch C improve from 3 to 2 when we reach B — it just gets a fresh copy in bucket 2, and the stale bucket-3 copy is skipped later. The sweep keeps climbing until every bucket is empty.

Pseudocode

dist[source] = 0, all others = infinity
buckets = array of empty lists, size n*W + 1
buckets[0].append(source)
for d = 0, 1, 2, ... up to the last bucket:
    while buckets[d] is not empty:
        u = pop from buckets[d]
        if d > dist[u]:           # a stale, outdated copy
            skip it
        for each (v, w) leaving u:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                buckets[dist[v]].append(v)
return dist

The Python solution

def dial(graph, source, W):
    # graph[u] = list of (v, weight); W = max edge weight
    n = len(graph)
    dist = [INF] * n
    dist[source] = 0
    buckets = [[] for _ in range(n * W + 1)]
    buckets[0].append(source)
    for d in range(len(buckets)):
        while buckets[d]:
            u = buckets[d].pop()
            if d > dist[u]:        # stale entry, skip
                continue
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    buckets[dist[v]].append(v)
    return dist

• dist holds the best distance known to each vertex; the source starts at 0 and the rest at infinity.
• buckets has one slot per reachable distance, 0 through n·W — that bound is what keeps the array finite.
• The outer for d loop is the heap replacement: it sweeps distances in increasing order, so buckets[d] is always the lowest non-empty bucket when it has anything in it.
• if d > dist[u] discards stale copies — a vertex that was later improved is sitting in an earlier, smaller bucket already settled.
• The relax block appends an improved vertex straight into buckets[dist[v]], no comparisons needed.

Complexity

When W is small, O(V·W + E) beats the log V heap and the code is shorter. The cost is the bucket array: its size scales with the maximum distance, so Dial only pays off for small integer weights.

When this pattern shows up

Practice