0-1 BFS's own Pitfalls section names this gap directly:
its two-ended deque trick "does generalize to a small, bounded range of integer weights by
swapping the two-ended deque for an array of several buckets, one per reachable distance — not
built as its own entry here." Dial's algorithm (Robert Dial, 1969) is that
generalization. When every edge cost is a small non-negative integer no larger than some bound
C — not just 0 or 1 — a two-ended deque isn't enough to keep the frontier sorted, but
a circular array of C + 1 buckets is: replacing Dijkstra's O(log V) heap operations with plain
array indexing, in exchange for assuming edge weights never exceed C.
Click a cell to cycle its cost through 0 → 1 → 2 → 3 (green is the start, orange is the end — fixed, always cost 1). The default terrain has a costly band across the middle (2/3/2) and a free walkway near the top. Step through the search and watch the bucket strip below the grid: four boxes, one per possible remainder mod 4 — the currently-active bucket is outlined, and each relaxed cell gets pushed into the bucket matching its new distance mod 4, not its raw distance. Watch the outline sweep left to right and wrap back around to bucket 0 as the search progresses past distance 3 — the same physical box holds distance 0, then later distance 4, then distance 8, and so on, never colliding because by the time it's reused the earlier occupant has always already been popped.
The whole method rests on one window argument: whenever a cell is popped at bucket index
idx, every relaxation it triggers pushes a neighbor at distance somewhere in
idx .. idx + C — never less (edges are non-negative), never more (no edge
costs more than C). That's a range of exactly C + 1 distinct values, which
is exactly the buffer's size, so two live entries can never land in the same physical slot at the
same time: by the time the sweep comes back around to reuse a slot, every entry that was ever placed
there has a distance small enough that it must already have been popped. Sweeping the index forward
one at a time and popping from whichever bucket it currently points at therefore visits cells in
non-decreasing distance order, exactly like Dijkstra's heap, without ever comparing two distances
against each other — the array position is the comparison.
One consequence worth noticing, shared with Dijkstra and 0-1 BFS: a cell can be pushed more than
once, and the stale, more-expensive entry is simply popped and skipped once reached, since the cell
is already finalized with a better distance by then. A subtler consequence is specific to this
structure: unlike a heap or deque, which naturally runs empty when the search is done, a bare
"advance idx until its bucket is non-empty" loop has no built-in stopping condition — on
a graph with unreachable cells, every bucket can be empty forever and the sweep would spin
indefinitely. The reference implementation below tracks a separate pending count
(incremented on every push, decremented on every pop, regardless of whether that pop turns out to be
stale) and stops once it hits zero — the one piece of bookkeeping a plain "keep sweeping" description
of the algorithm tends to leave out.
Grid version, tracking a parent pointer per cell exactly like Dijkstra and 0-1 BFS, relaxing
through a small-integer cost grid into a circular array of maxWeight + 1 buckets:
function dialsAlgorithm(grid, rows, cols, start, end, maxWeight) {
const key = (r, c) => r * cols + c;
const n = rows * cols;
const dist = new Array(n).fill(Infinity);
const finalized = new Array(n).fill(false);
const parent = new Array(n).fill(-1);
const startK = key(...start), endK = key(...end);
dist[startK] = 0;
// Circular buffer: any relaxation out of a cell popped at index `idx`
// lands somewhere in idx..idx+maxWeight, a window exactly maxWeight + 1
// wide — so a buffer that size can never alias two live entries.
const numBuckets = maxWeight + 1;
const buckets = Array.from({ length: numBuckets }, () => []);
buckets[0].push(startK);
let pending = 1, idx = 0;
while (pending > 0) {
while (buckets[idx % numBuckets].length === 0) idx++;
const cur = buckets[idx % numBuckets].pop();
pending--;
if (finalized[cur]) continue; // stale duplicate, already finalized cheaper
finalized[cur] = true;
if (cur === endK) break;
const r = Math.floor(cur / cols), c = cur % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nk = nr * cols + nc;
if (finalized[nk]) continue;
const w = grid[nk]; // 0..maxWeight: the cost to enter that cell
const nd = dist[cur] + w;
if (nd < dist[nk]) {
dist[nk] = nd;
parent[nk] = cur;
buckets[nd % numBuckets].push(nk);
pending++;
}
}
}
if (!finalized[endK]) return null; // unreachable
const path = [];
for (let cur = endK; cur !== -1; cur = parent[cur]) path.push(cur);
return { path: path.reverse(), cost: dist[endK] };
}Verified against a from-scratch Dijkstra reference: 3,000 random grids up to 8×8 with random integer weights from 0 up to a random bound (1 to 4), every one agreeing on the exact cost to the far corner, plus a check that the reconstructed path only steps between grid-adjacent cells and its own summed weights match the reported cost — zero mismatches, zero invalid reconstructions.
Sizing the buffer to C instead of C + 1. It's an easy
off-by-one to make — "the weights go from 0 to C, so there are C of them" —
but the window argument above needs a slot for every value in idx..idx+C inclusive, which
is C + 1 values. Shrink the buffer by one and a bucket gets reused one distance early:
a fresh entry lands in the same physical slot an older, still-pending entry already occupies, gets
popped prematurely (its idx doesn't match its real distance yet, so the stale-check
discards it), and is gone for good — not requeued, just lost. A concrete case: three nodes, edge
0→1 costing 2 and edge 1→2 costing 0, C = 2. The correct distances are
[0, 2, 2]. With a 2-slot buffer instead of 3, node 1's distance-2 entry gets pushed into
slot 2 % 2 = 0 — the same slot node 0 just vacated — and popped immediately while
idx is still 0, where the mismatched-distance check throws it away as a false stale
duplicate; node 2 never gets discovered at all, reported unreachable. Tested against 5,000 random
trials: wrong on 17.2% of them, not a rare edge case.
It's a net loss once C is large relative to the graph. Not a
correctness bug — a performance one, and purely a matter of how big C is, not how big
the graph is. On this page's own 7×11 demo grid, capping costs at C = 4 (matching the
demo), Dial's algorithm does 244 bucket operations against a linear-scan priority
queue's 717 — a clear win. Widen the cap to C = 500 on that same
77-cell grid, keeping every other shape identical, and it flips: Dial's algorithm now does
2,702 operations against the priority queue's unchanged 860 — over
3x more, because the circular buffer's sweep is proportional to the final distance reached, which
now dwarfs the vertex count. The bound that makes this algorithm fast — total work
O(E + VC) — is the same bound that makes it slow the moment C stops being
small.
Time: O(E + VC), where C is the largest edge weight.
Every vertex is popped once and every edge relaxed once, both O(1) work given array
indexing — that part is O(V + E), identical to BFS. What BFS and 0-1 BFS don't pay for
is the index sweep: across the whole run, idx only ever increases, and it can climb as
high as the largest finalized distance, which is at most (V - 1) · C — hence the
+ VC term, the price of using array position instead of a real comparison. 0-1 BFS is the C = 1 special case, where that term
collapses to just V and disappears into the existing O(V + E).
Space: O(V + E + C) — the distance, finalized, and parent arrays plus
the bucket array, which needs exactly C + 1 slots regardless of how large the graph
is.
For a decision guide across all thirteen of this site's shortest-path entries — which one to reach for depending on negative edges, single-source vs. all-pairs, a heuristic, or edge weights this restricted — see Choosing a Shortest-Path Algorithm.