Dial's Algorithm

Purpose: Shortest paths when all edge weights are small non-negative integers $\le C$, in $O(VC+E)$ — replacing Dijkstra’s priority queue with an array of buckets.

The Idea

Dijkstra spends $O(\log V)$ per operation maintaining a heap ordered by distance. If distances are bounded by $D=(V-1)C$, you can instead keep an array bucket[0..D] where bucket[d] holds the vertices at tentative distance $d$, and sweep $d$ upward. Each bucket access is $O(1)$.

vector<int> dial(int n, int s, vector<vector<pair<int,int>>>& adj, int C) {
    int D = (n - 1) * C;
    vector<int> dist(n, INT_MAX);
    vector<vector<int>> bucket(D + 1);
    dist[s] = 0;
    bucket[0].push_back(s);
 
    for (int d = 0; d <= D; d++) {
        while (!bucket[d].empty()) {
            int u = bucket[d].back(); bucket[d].pop_back();
            if (dist[u] != d) continue;                 // stale entry
            for (auto [v, w] : adj[u])
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    bucket[d + w].push_back(v);
                }
        }
    }
    return dist;
}

Circular buckets — the memory fix

The full array is $O(VC)$, which can be huge. But at any moment the live distances span only $[d,d+C]$, so $C+1$ buckets suffice if you index them modulo $C+1$:

vector<vector<int>> bucket(C + 1);
// insert v at distance nd:  bucket[nd % (C + 1)].push_back(v);

This brings the space down to $O(V+C)$ and is the version worth writing.

Complexity comparison

Weights	Algorithm	Time
all 1	BFS	$O(V+E)$
$\{0,1\}$	0-1 BFS	$O(V+E)$
$[0,C]$ integers, $C$ small	Dial	$O(VC+E)$ or $O(E+VC)$ with circular buckets
arbitrary non-negative	Dijkstra	$O(E\log V)$
arbitrary, Fibonacci heap	Dijkstra	$O(E+V\log V)$
integers, word RAM	Thorup	$O(E)$ — theoretical

Dial wins when $C\le \log V$ roughly; beyond that the bucket sweep costs more than the heap.

Where it appears

• Small integer costs — grids where each move costs 1-5, edge colours with small penalties
• Radix heaps — the generalisation: buckets by the highest differing bit, giving $O(E+V\log C)$ Dijkstra
• Timetable and routing problems with discretised times
• 0-1 BFS — the $C=1$ special case, where two buckets (a deque) suffice

Practical note

In a contest, Dijkstra with priority_queue handles $E=10^6$ in well under a second, so Dial is rarely necessary. Its value is knowing that “the priority queue is the only slow part” and that bounded weights let you delete it. The same insight produces the deque in 0-1 BFS, which is commonly needed.

See also: 0-1 BFS · Dijkstra · Shortest Paths