vault

01-BFS

17 min read

0-1 BFS

0-1 BFS is a shortest-path algorithm for graphs whose edge weights are restricted to the set {0, 1}. It runs in O(V + E) time — strictly better than Dijkstra’s Algorithm’s O((V + E) log V) — by replacing Dijkstra’s priority queue with a double-ended queue (deque). The single insight: when relaxing an edge (u, v) with weight w, if w == 0 push v to the front of the deque; if w == 1 push to the back. This preserves the layer property that makes BFS correct, because a 0-weight edge means v belongs in the same conceptual layer as u, while a 1-weight edge advances to the next layer. 0-1 BFS is the right tool for grid problems where some moves are “free” (portals, conveyor belts, gravity drops) and others cost one step, for binary state-transition graphs, and for any problem where edges naturally bifurcate into “free” and “unit-cost.”

1. Intuition — A Conveyor Belt in a Warehouse

Imagine a warehouse where you need to walk from station A to station B. Most movement costs you one step (one unit of energy). But some sections have conveyor belts that carry you forward for free — stepping onto a belt costs nothing extra; the belt does the moving.

If you ran plain BFS, you’d treat conveyor-belt steps and walking steps identically (both cost 1), so the algorithm would prefer paths that minimise total number of edges, not total energy. That’s wrong: a path with 50 conveyor-belt edges and 5 walking edges costs 5, but plain BFS might pick a path with 0 conveyor-belt edges and 7 walking edges (cost 7) just because it has fewer total edges.

You could run Dijkstra, paying the log V factor for the priority queue. But because all weights are either 0 or 1, the priority queue is overkill: the only “priority” is “is this the same layer as the current node, or one layer further?” That binary distinction can be encoded by which end of the deque you push to — front for “same layer” (0 cost), back for “next layer” (1 cost).

The deque, processed front-to-back, naturally produces nodes in non-decreasing distance order. That’s the BFS layer property restored, and you avoid the heap. O(V + E) time, no logs.

2. Tiny Worked Example

A 3×3 grid where each cell has cost-to-enter; arrows show edge directions and weights. We want shortest cost from top-left S to bottom-right T:

S(*) -1-> a -0-> b
 |         |     |
 1         0     1
 v         v     v
 c -1-> d(*) -0-> e
 |         |     |
 0         1     1
 v         v     v
 f -0-> g -1-> T

(Asterisks * mark cells with multiple in/out edges; this is just an example, not a real grid.)

Equivalent edge list (directed):

S→a (1)   S→c (1)
a→b (0)   a→d (0)
b→e (1)
c→d (1)   c→f (0)
d→e (0)   d→g (1)
e→T (1)
f→g (0)
g→T (1)

Run 0-1 BFS from S:

StepDeque (front → back)dist map (only finalised)Action
Init[S]S:0start
1[a, c]S:0, a:1, c:1pop S; relax a (1, push back), c (1, push back)
2[b, d, c]S:0, a:1, b:1, d:1, c:1pop a; relax b (0, push front), d (0, push front)
3[d, c, e]+ e:2pop b; relax e (1, push back)
4[c, e, g]+ g:2pop d; e already 1+0=1? No, S→a→d=1, d→e=0 → e=1, better than 2, update; relax g (1, push back)

Wait — let me redo step 4 more carefully. After step 3: dist = {S:0, a:1, b:1, c:1, d:1, e:2}, deque = [d, c, e].

Step 4: pop d. dist[d]=1. Edge d→e weight 0: candidate dist 1+0=1, beats current dist[e]=2 → update dist[e]=1, push e to front of deque (because weight 0). Edge d→g weight 1: candidate 1+1=2, dist[g] uninit → dist[g]=2, push g to back.

Deque after step 4: [e, c, e(stale), g]. Wait, e is pushed twice: once at step 3 (with stale dist 2) and once at step 4 (with current dist 1). Both entries sit in the deque.

This is the stale-entry phenomenon of lazy deletion, exactly as in Dijkstra. We handle it the same way: when we pop (u, d) and find d > dist[u], we skip.

Actually, in 0-1 BFS we typically don’t store the distance with the node — the deque holds just nodes — and we re-check if visited[u]: continue at pop time. But for correctness, we need an enqueue-then-relax discipline that doesn’t suffer:

The cleanest implementation (see §4) tracks dist and skips when popping reveals an out-of-date dist.

Final answer: shortest cost S → T = S(0) → a(1) → d(1) → e(1) → T(2) = total weight 2 (S→a=1, a→d=0, d→e=0, e→T=1). 0-1 BFS finds this without a heap.

3. Pseudocode

zero_one_bfs(graph, source):
    dist := map; dist[source] := 0; all others := ∞
    deque := empty double-ended queue
    push source onto FRONT of deque
    while deque is not empty:
        u := pop FRONT
        for each (v, w) in adjacency(u):
            if dist[u] + w < dist[v]:
                dist[v] := dist[u] + w
                if w == 0:
                    push v onto FRONT
                else:                    # w == 1
                    push v onto BACK
    return dist

The whole algorithm is the standard BFS skeleton with two lines changed: the deque (instead of a queue) and the front/back push decision based on weight.

4. Python Implementation

from collections import deque
 
def zero_one_bfs(graph, source):
    """
    graph: dict node -> list of (neighbour, weight in {0, 1})
    Returns: dict node -> shortest path cost from source
    """
    INF = float('inf')
    dist = {source: 0}
    dq = deque([source])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            nd = dist[u] + w
            if nd < dist.get(v, INF):
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)     # 0-edge: same layer
                else:
                    dq.append(v)         # 1-edge: next layer
    return dist

The implementation is a one-character difference from BFS — deque.appendleft for 0-weight, deque.append for 1-weight. Yet the semantics are wholly different: BFS computes “shortest number of edges”; 0-1 BFS computes “shortest sum of {0,1} weights.”

Grid version

def shortest_grid_path(grid, source, target):
    """
    grid[r][c] in {'.', 'X', '0'}: '.' = normal cell (cost 1 to enter),
        'X' = blocked, '0' = portal (cost 0 to enter from any neighbour).
    Returns: minimum cost from source to target.
    """
    R, C = len(grid), len(grid[0])
    INF = float('inf')
    dist = {source: 0}
    dq = deque([source])
    DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
    while dq:
        r, c = dq.popleft()
        if (r, c) == target:
            return dist[(r, c)]
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != 'X':
                w = 0 if grid[nr][nc] == '0' else 1
                nd = dist[(r, c)] + w
                if nd < dist.get((nr, nc), INF):
                    dist[(nr, nc)] = nd
                    if w == 0:
                        dq.appendleft((nr, nc))
                    else:
                        dq.append((nr, nc))
    return INF

Why no explicit visited set?

The if nd < dist.get(v, INF) check serves dual duty: it both (a) prevents re-relaxation when the new distance isn’t strictly better, and (b) plays the role of “visited” — if we’ve already reached v with the optimal distance, no future pop of a stale v entry will improve it. Stale entries in the deque are skipped implicitly because their relaxation step won’t improve any neighbour’s dist.

Some implementations use an explicit visited set checked at pop time; this is slightly more memory but easier to reason about. Either works.

5. Complexity

For a graph with V vertices and E edges, all weights in {0, 1}:

  • Time: O(V + E). Each vertex is finalised at most once. Each edge is relaxed at most twice (once when its source is first popped, possibly once more if a better distance to the source is found later — but with the if nd < dist[v] guard, redundant work is bounded). The deque operations appendleft, append, popleft are all amortised O(1) for a doubly-linked-list-backed deque (Python’s collections.deque uses a block-array representation with the same O(1) amortisation).
  • Space: O(V). The deque can hold up to V entries in the worst case (similar to BFS); the dist map holds up to V entries.

Why not O((V + E) log V) like Dijkstra?

Dijkstra’s log V factor comes from the priority queue: each push/pop costs O(log n) where n is heap size. 0-1 BFS replaces the priority queue with a deque, which has O(1) push/pop. The reason this is correctness-preserving is that with only two possible weights, “priority” reduces to a binary choice and the deque encodes it perfectly.

If you tried to extend 0-1 BFS to weights {0, 1, 2} by adding a “middle” position to the deque, you’d find there is no constant-time data structure with three insertion ends. The natural generalisation is Dial’s algorithm (a bucket-based shortest-path algorithm for small-integer weights) which works for weights {0, 1, ..., C} in O(VC + E) time using C+1 buckets. Beyond small C, you’re back to Dijkstra.

Compare to alternatives

AlgorithmEdge weightsComplexity
Breadth-First Searchunweighted (= all 1)O(V + E)
0-1 BFS{0, 1}O(V + E)
Dial’s algorithm{0, ..., C}O(V·C + E)
Dijkstra’s Algorithmnon-negative realsO((V + E) log V)
Bellman-Fordany reals (incl. negative)O(V·E)

For {0, 1} graphs specifically, 0-1 BFS is strictly the right choice — Dijkstra works but is asymptotically slower by a log V factor.

6. Why It Works — Correctness Proof

Claim: at the moment a vertex u is popped from the front of the deque, dist[u] is its true shortest-path distance from source.

Proof sketch. By induction on the pop order. Consider the deque at any moment: the entries, read front-to-back, are in non-decreasing order of dist. Specifically:

Invariant: at any moment, if entries [v_1, v_2, ..., v_k] are in the deque (front to back), then dist[v_i] ≤ dist[v_{i+1}] for all i, and dist[v_k] - dist[v_1] ≤ 1.

Why the invariant holds: initially the deque holds just source with dist=0, trivially satisfying both. When we pop u with dist[u] = D, and relax edges:

  • A 0-weight relaxation gives dist[v] = D. We push v to the front; the new front has dist = D, the old front had dist ≥ D, so the order is preserved. (Actually, the old front-most entry had dist ≤ D + 1; pushing v with dist = D keeps the invariant because D ≤ old front.)
  • A 1-weight relaxation gives dist[v] = D + 1. We push v to the back; the back’s previous entry had dist ≤ D + 1 (by the invariant dist_back - dist_front ≤ 1, and dist_front ≥ D after the pop). So pushing v with dist = D + 1 keeps the back monotone.

Because dist is non-decreasing in pop order, the first time we pop u we have dist[u] set to the smallest distance any path could give it. (Any shorter path would have to pass through some vertex w not yet popped, but dist[w] < dist[u] would mean w should have been popped earlier — contradiction.) ∎

The invariant is the algorithmic analog of Dijkstra’s monotonicity argument; the deque simulates a priority queue with two priority levels.

The invariant, stated precisely. Per cp-algorithms, if v is the vertex at the front of the deque with distance d[v], then every vertex u currently in the deque satisfies d[v] ≤ d[u] ≤ d[v] + 1. Equivalently: at most two distinct distance values are present in the deque at any moment — call them D and D+1 — with all entries of distance D appearing in a contiguous prefix and all entries of distance D+1 appearing in the contiguous suffix. The two formulations (“non-decreasing with span ≤ 1” and “at most two distinct distance values, prefix-then-suffix”) are equivalent — the second is just a structural restatement of the first.

This is exactly what makes the algorithm correct without a priority queue: popping the front always returns a vertex whose distance is the minimum among all enqueued vertices, which is the Dijkstra monotonicity property restricted to a two-level priority. If you experiment with implementation variants (batching pushes, deferred relaxation, lazy decrease-key), you must verify this invariant survives — the most common bug is to push to the wrong end and end up with d[u] = d[v] + 2 somewhere in the deque, which breaks the proof and silently produces wrong distances.

7. Use Cases

7.1 Grids with portals or teleporters

Classic problem shape: a grid where most moves cost 1 step, but some special cells (portals, slides, conveyor belts, free-ride vehicles) let you transition for free. The graph has 1-weight edges for normal moves and 0-weight edges for “step onto portal” moves.

7.2 Minimum cost to make a path valid (LeetCode 1368)

Each grid cell has an arrow pointing in a direction. Moving in the indicated direction costs 0; moving in a different direction costs 1 (the cost of “rewriting” the arrow). Find the minimum-cost path from (0, 0) to (m-1, n-1). This is the canonical 0-1 BFS interview problem; it’s nearly impossible to solve cleanly without recognising the {0, 1}-weight structure.

7.3 Minimum number of obstacle removals to reach goal (LeetCode 2290)

Grid with empty cells (cost 0 to enter) and obstacle cells (cost 1 to enter, since you have to remove the obstacle). Find the minimum total cost to traverse from corner to corner. Direct 0-1 BFS application.

7.4 String transformation with free operations

If you can transform string s to string t with operations of cost 0 (e.g., character substitution from a free pool) and cost 1 (every other operation), 0-1 BFS computes the minimum cost. Plain edit distance is more general but more expensive; if your operation costs naturally fall into {0, 1}, 0-1 BFS often beats DP.

7.5 Logical formulae (2-SAT, implication graphs)

Some logical-implication problems on directed graphs can be reduced to “shortest implication chain” where some implications are “free” (definitionally true) and others cost 1 (require an external assumption). Niche but elegant when it fits.

If a network has two link types — “trunk” (free, high-bandwidth) and “edge” (one unit cost, low-bandwidth) — the cheapest route is a 0-1 BFS problem.

8. Variants

8.1 Multi-source 0-1 BFS

Same trick as Multi-Source BFS: initialise the deque with all sources at distance 0. The correctness argument is unchanged.

8.2 Bidirectional 0-1 BFS

Combine 0-1 BFS with Bidirectional BFS. Termination becomes subtler: you can’t stop at first frontier intersection because a 0-weight chain might give a better path. Workable but rarely worth the complexity in practice.

8.3 Dial’s algorithm — generalisation to small weights

For weights in {0, 1, ..., C}, maintain C+1 buckets indexed by current distance modulo C+1. Pop from bucket d; push to bucket (d + w) mod (C+1). Runs in O(V·C + E). For very small C (≤ 10), Dial’s beats Dijkstra; for larger C, Dijkstra wins.

8.4 Generalised 0-K BFS using radix heap

A radix heap supports O(log C) push/pop for integer weights bounded by C, giving O((V + E) log C) shortest paths. Rarely seen in interviews; common in advanced competitive programming.

9. Pitfalls

9.1 Using appendleft for the wrong weight

The classic 0-1 BFS bug: swapping appendleft and append so that 1-weight edges go to the front. This breaks the layer property and produces wrong distances. Mnemonic: 0 means “stay in this layer” (front, will be processed before any 1-edge that came earlier); 1 means “advance to next layer” (back).

9.2 Forgetting the relaxation guard

# WRONG — pushes every neighbour every time, blowing up to O(V·E) or worse
for v, w in graph[u]:
    if w == 0: dq.appendleft(v)
    else:      dq.append(v)
    dist[v] = dist[u] + w

Without the if nd < dist.get(v, INF) check, you re-push and re-process vertices repeatedly with no improvement. Always guard the push with the strict-improvement check.

9.3 Mutable default argument for dist

def zero_one_bfs(graph, source, dist={}):  # TRAP

Python evaluates default arguments once at definition time. Reusing the same dist across calls leaks state. Use dist=None and initialise inside.

9.4 Treating “very small weight” as 0

If you pre-process edge weights to round small values to 0 hoping to apply 0-1 BFS, you change the answer. The algorithm requires weights exactly in {0, 1}. For other weights use Dijkstra.

9.5 Negative weights

0-1 BFS does not handle -1-weight edges. If you encounter a problem with {-1, 0, 1} weights, either reformulate (often possible by choosing a different graph encoding) or use Bellman-Ford.

9.6 Stale entries skipped at pop time vs at relax time

Two implementation styles:

Style A (skip at relax): only enqueue if nd < dist[v]. Stale entries never enter the deque.

Style B (skip at pop): enqueue freely; on pop, check if (computed dist somehow) > dist[u]: continue. This needs storing distance with the deque entry, like Dijkstra’s lazy variant.

Both are correct. Style A is what the Python implementation in §4 uses and what cp-algorithms presents. Style B feels more familiar to people coming from Dijkstra. Mixing the two styles in one implementation is a common source of bugs. Pick one.

9.7 Confusing “BFS with unit weights” with “0-1 BFS”

Plain BFS is correct for all-1 graphs. 0-1 BFS is correct for {0, 1} graphs. The difference is the existence of zero-weight edges; without them, 0-1 BFS is just plain BFS with a deque pretending to be a queue.

10. Diagram — Deque State During 0-1 BFS

flowchart LR
  subgraph DQ["Deque (front → back)"]
    direction LR
    F[v at dist=D] --- N1[w at dist=D] --- N2[x at dist=D+1] --- B[y at dist=D+1]
  end
  POP[Pop front: v] -.dist=D.-> DQ
  R0[Relax 0-edge to z: appendleft] -.->|push z dist=D to FRONT| DQ
  R1[Relax 1-edge to t: append] -.->|push t dist=D+1 to BACK| DQ

What this diagram shows. At any moment during 0-1 BFS execution, the deque holds vertices in non-decreasing distance order, and the spread between the front-most and back-most distances is at most 1. When a vertex v is popped from the front (with dist=D):

  • Relaxing a 0-weight edge v → z finds z at the same distance D and pushes z to the front. The front retains dist=D.
  • Relaxing a 1-weight edge v → t finds t at distance D+1 and pushes t to the back. The back retains dist=D+1.

Both operations preserve the invariant. Reading the deque front-to-back gives nodes in shortest-distance-first order — exactly what BFS needs to be correct, achieved without a priority queue. The two ends of the deque correspond conceptually to “this layer” and “next layer.”

11. Common Interview Problems

LeetCode #ProblemWhy 0-1 BFS
1368Minimum Cost to Make at Least One Valid Path in a GridMatch-arrow = 0, change-arrow = 1
2290Minimum Obstacle Removal to Reach CornerEmpty = 0, obstacle = 1
1293Shortest Path with K Obstacle Removals (variant)Often modelled as state-augmented BFS; 0-1 BFS variant possible
2577Minimum Time to Visit a Cell in a GridSubtler — uses min-time + parity, not pure 0-1 BFS, but related
Codeforces 173B (Chamber of Secrets)Mirror placement to redirect light beamCanonical 0-1 BFS competitive-programming problem

The interview tell: weights are exactly 0 and 1, and the problem has a sense of “free moves” versus “costly moves.” If you spot this and propose 0-1 BFS, you’ve immediately distinguished yourself from candidates who reach for Dijkstra reflexively.

12. Open Questions

  • Can 0-1 BFS be parallelised cleanly? The deque’s two-ended structure makes it harder to shard than a simple FIFO queue.
  • When the graph has a small set of weight values (e.g., {0, 1, 1000}) and you can ignore the high-weight edges except as last resort, does a 0-1 BFS variant make sense? (Probably yes — partition the search into 0-1 BFS within the dense subgraph and Dijkstra at the boundaries.)

13. See Also

Graph View

Backlinks