↩ back to Shortest Paths

0-1 BFS

Breadth-first search's FIFO queue only gives a shortest-path guarantee because every edge secretly costs the same "one step." Dijkstra's algorithm fixes that for edges of any cost, but pays for it with a full priority queue. There's a narrower case worth its own algorithm: every edge costs exactly 0 or 1, nothing else — a free move (a shared boundary, a teleport, an escalator) sitting alongside an ordinary one. A deque — a queue open at both ends — is exactly the structure that case needs: push a newly-discovered 0-cost neighbor onto the front, since it's tied with the node just finished and has to come out next, and push a 1-cost neighbor onto the back, since it waits behind everything already queued. No heap, no O(log n) per edge — the same O(V + E) bound plain BFS already gets, for a graph one notch richer than BFS can handle on its own.

Try it

Click a cell to toggle it between snow (costs 1 to enter) and ice (free to enter — green is the start, orange is the end, fixed at cost 1). The default board has a frozen lake in the middle: walking around it costs 16, but cutting across it costs only 7, even though the lake sits nowhere near a straight line between start and end. Step through the search and watch the deque below the grid: a push onto the front (an ice cell just discovered) jumps to the head of the line, a push onto the back (a snow cell) waits behind everything already queued, and the cell popped from the front each step gets a bold border.

Why it works

The invariant is a slightly loosened version of BFS's own: at any point during the search, every distance still sitting in the deque is either the smallest finalized distance so far, call it d, or exactly d + 1 — never anything larger. That holds by induction: the only way to discover a node is by relaxing a 0- or 1-cost edge out of some already-finalized node, whose own distance is d or less, so the new distance is d or d + 1. Because 0-cost pushes go to the front and 1-cost pushes go to the back, the deque naturally sorts itself into two contiguous runs — every d-cost entry ahead of every d + 1-cost entry — without ever comparing two distances directly or paying for a heap. Popping from the front therefore always yields a node whose distance is already minimal, exactly like plain BFS's FIFO does for hop count, generalized to tolerate a same-or-next tier instead of insisting on strictly-next.

One consequence worth noticing in the demo, shared with Dijkstra: a node can be pushed onto the deque more than once. If a cheaper route to an already-queued node is found later, the new (lower) distance is pushed as a fresh entry rather than modifying the old one in place. The stale, more expensive entry is left sitting in the deque and simply popped and skipped once it's reached, since the node is already finalized with a better distance by then — wasted deque space, not a correctness problem.

Reference implementation

Grid version, tracking a parent pointer per cell exactly like BFS and Dijkstra. The deque itself is a fixed-size array with two indices that grow toward each other from opposite ends, so pushFront, pushBack, and popFront are all O(1) — see Pitfalls below for why a plain array's built-in unshift()/shift() won't do:

function zeroOneBFS(grid, rows, cols, start, end) {
  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;

  // buf grows outward from the middle: pushFront does buf[--lo], pushBack
  // does buf[hi++], popFront does buf[lo++]. Capacity is generous — at most
  // one push per edge, in either direction.
  const cap = 4 * n;
  const buf = new Array(2 * cap + 1);
  let lo = cap, hi = cap;
  buf[hi++] = startK;

  while (lo < hi) {
    const cur = buf[lo++];
    if (finalized[cur]) continue; // stale entry, 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 or 1: the cost to enter that cell
      const nd = dist[cur] + w;
      if (nd < dist[nk]) {
        dist[nk] = nd;
        parent[nk] = cur;
        if (w === 0) buf[--lo] = nk; else buf[hi++] = nk;
      }
    }
  }

  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 0/1 weights, every one agreeing on the exact cost to every cell, plus a check that the reconstructed path only steps between grid-adjacent cells and its own summed weights match the reported cost — zero mismatches.

Pitfalls

Pushing to the wrong end. Swap which end each cost goes to — a 0-cost neighbor onto the back, a 1-cost neighbor onto the front — and the algorithm still runs and still terminates, it just quietly stops being correct: the deque no longer sorts itself into ascending distance tiers, so a node can be finalized before a cheaper route to it has even been discovered. Testing the swapped version against the same Dijkstra reference found it disagreeing on the final cost in 792 of 1,000 random trials (79.2%) — not a rare edge case, the dominant outcome. One concrete instance: a 3×6 grid where the correct cost to the far corner is 2, and the swapped version reports 3, both runs on the exact same terrain.

A plain array's unshift()/shift() is O(n) per call — same shape as the O(1)-per-dequeue trick BFS's own reference implementation leans on, just needed at both ends here instead of one. Using them anyway would turn every front-push into a full array shift, degrading the whole algorithm from O(V + E) toward O(V² + E) on a graph where discoveries are pushed to the front often. The fixed-buffer trick above (or a real doubly linked list) keeps both ends O(1); the demo's own stepper still uses unshift()/push() for clarity, the same trade Dijkstra's demo makes with a linear-scan priority queue instead of a heap.

It stops working the moment a third edge cost shows up. The two-tier argument above depends entirely on every edge being 0 or 1 — a single edge costing 2 breaks the "never more than d + 1 apart" invariant the whole proof rests on, and Dijkstra's full priority queue becomes necessary again. (The same 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, since 0-1 BFS's clean two-bucket case already carries the whole argument.)

Complexity

Time: O(V + E) — every vertex is popped once and every edge is relaxed at most once, with O(1) work per relaxation given the fixed-buffer deque. On an r × c grid, V = r·c and each cell has at most 4 edges, so this is O(r·c), identical to plain BFS's bound and a full log V factor cheaper than Dijkstra's O((V + E) log V) — the deque buys back exactly the cost a general priority queue adds, in exchange for assuming edges are only ever 0 or 1. Space: O(V + E) for the distance array, the finalized array, the parent array, and the deque's buffer, which needs enough room for one entry per edge in the worst case rather than just one per vertex.

For a decision guide across all eleven 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.