How to Learn 0–1 BFS: Binary Edge Weights, Deques, Distance Invariants and Linear-Time Shortest Paths

What if a graph is weighted, but every edge costs only 0 or 1? Ordinary breadth-first search is no longer sufficient because not every step has the same cost. A full priority queue, however, is more machinery than the weight structure demands. 0–1 BFS occupies the elegant middle ground: it uses a deque to process zero-cost moves immediately and one-cost moves just behind them.

This article teaches 0–1 BFS as a Learning Hall progression from ordinary BFS to professional shortest-path engineering. It complements the broader Graph Algorithms foundation and the more parallel Delta-Stepping article rather than replacing either job.

Quick Read

0–1 BFS solves single-source shortest paths when every edge weight is exactly 0 or 1.
It uses a deque instead of a heap.
If a relaxation uses a weight-0 edge, push the destination to the front.
If a relaxation uses a weight-1 edge, push the destination to the back.
The deque preserves the same useful priority ordering that Dijkstra would create for binary weights.
With adjacency lists, the standard algorithm runs in O(V + E) time and O(V + E) storage including the graph.
Do not replace distance relaxation with a simple “visited once” rule; a vertex can be discovered and later improved.

1. Beginner Level: Why Ordinary BFS Stops Working

In an unweighted graph, every edge costs the same. BFS processes vertices by number of edges from the source, so the first time it reaches a vertex, it has found a shortest path in that metric.

Now give some edges cost 0 and others cost 1. A path containing five zero-cost edges can be cheaper than a path containing one cost-1 edge. Counting hops is no longer enough. We need to order work by accumulated cost, not simply by how many edges have been traversed.

2. Why the Weights 0 and 1 Are Special

Dijkstra’s algorithm normally uses a priority queue because tentative distances can differ by many values. With only 0 and 1 edges, a vertex with current distance d can relax neighbours only to d or d + 1.

That narrow distance range means we do not need a general-purpose heap to keep the smallest tentative distance at the front. A double-ended queue is enough. New distance-d work goes to the front; new distance-(d+1) work goes to the back.

3. The Deque Rule

For an edge u → v with weight w:

compute candidate = dist[u] + w;
if candidate is not better than dist[v], do nothing;
if candidate improves dist[v], update it;
if w = 0, push v to the front of the deque;
if w = 1, push v to the back.

The push direction is the whole algorithmic trick. A free transition deserves immediate attention because it does not increase distance. A cost-1 transition belongs behind all work that can still be completed at the current distance.

4. The Key Distance Invariant

Suppose the front of the deque has distance d. Under the standard 0–1 BFS process, pending useful vertices are ordered so that distance-d work appears before distance-(d+1) work. There is no need for a pending distance d+7 because one relaxation can increase distance by at most 1.

This is why the deque is acting like a specialised two-level priority queue. Understanding that invariant is more important than memorising appendleft and append.

5. A Small Worked Example

Consider these directed edges:

S -> A  weight 1
S -> B  weight 0
B -> C  weight 0
C -> A  weight 0
A -> T  weight 1

A hop-count view might focus on S → A quickly. But 0–1 BFS discovers B at cost 0 and pushes it to the front. B discovers C at cost 0, again at the front. C then improves A from cost 1 to cost 0. The cheapest route to T becomes S → B → C → A → T with total cost 1.

This example also shows why a Boolean “visited” array can be wrong if it freezes A when A is first discovered. Shortest-path algorithms need relaxation: a later route may improve a tentative distance.

6. Pseudocode

dist[*] = infinity
dist = 0
deque = 

while deque is not empty:
    u = pop_front(deque)

    for each edge (u, v, w):
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            parent[v] = u

            if w == 0:
                push_front(deque, v)
            else:
                push_back(deque, v)

There is no separate sorting step. Priority emerges from where each improved vertex is inserted.

7. Python Implementation

from collections import deque
from math import inf


def zero_one_bfs(graph, source):
    """
    graph[u] is an iterable of (v, weight), where weight is 0 or 1.
    Returns (dist, parent).
    """
    n = len(graph)
    dist = [inf] * n
    parent = [-1] * n

    dist = 0
    dq = deque()

    while dq:
        u = dq.popleft()

        for v, w in graph[u]:
            if w not in (0, 1):
                raise ValueError("0-1 BFS requires weights 0 or 1")

            candidate = dist[u] + w
            if candidate < dist[v]:
                dist[v] = candidate
                parent[v] = u

                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)

    return dist, parent

This version favours transparency. In a production setting, validate the weight domain before the hot loop when possible, choose compact graph storage, and measure whether Python object overhead matters for the expected graph size.

8. Reconstructing an Actual Shortest Path

Distances answer “how cheap?” but many applications also need “which route?” Record the predecessor whenever a relaxation improves a vertex.

def reconstruct_path(parent, source, target):
    path = []
    cur = target

    while cur != -1:
        path.append(cur)
        if cur == source:
            path.reverse()
            return path
        cur = parent[cur]

    return None  # target unreachable from source

If several shortest paths have equal cost, the returned path depends on adjacency order and tie behaviour. Distance optimality does not imply a unique route.

9. Why It Works: A Dijkstra View

Dijkstra repeatedly prefers the smallest tentative distance. For binary edge weights, relaxing a vertex at distance d can create only candidates d and d + 1. The deque places d candidates at the front and d + 1 candidates at the back, so the useful ordering is maintained without logarithmic heap operations.

Another way to see it is bucketed priority. At any moment, only a tiny number of adjacent distance buckets matter. 0–1 BFS is therefore a specialised bucket shortest-path algorithm whose bucket mechanism collapses neatly into a deque.

10. Complexity

With adjacency lists, the standard 0–1 BFS algorithm runs in O(V + E) time. Deque insertion and removal are O(1), and the binary-weight ordering prevents the logarithmic priority-queue factor of ordinary heap-based Dijkstra. Distance and parent arrays use O(V) additional storage; the adjacency lists use O(V + E).

As always, asymptotic notation is only the first layer. Real performance also depends on graph representation, cache locality, allocation, language overhead and whether the graph fits comfortably in memory.

11. Choosing the Right Shortest-Path Tool

All edges equal: ordinary BFS.
Weights only 0 and 1: 0–1 BFS.
Small non-negative integer weights: bucket methods such as Dial-style approaches may be attractive.
General non-negative weights: Dijkstra or a suitable specialised implementation.
Negative edges: 0–1 BFS is not applicable; use an algorithm designed for that model.
Parallel high-throughput weighted graphs: specialised methods such as Delta-Stepping may be worth studying.

The professional habit is to inspect the structure of the weights before choosing the data structure. A generic priority queue is powerful, but generic machinery can be unnecessary when the domain is highly constrained.

12. Modelling Problems as 0–1 Graphs

0–1 BFS becomes especially useful when the graph is not given directly but is constructed from choices. Examples include:

moving in a preferred direction costs 0, changing direction costs 1;
following an existing connection costs 0, creating or reversing one costs 1;
using a normal state transition costs 0, using an exception costs 1;
crossing a grid cell of one type costs 0 and another type costs 1;
keeping a configuration costs 0 while making a modification costs 1.

The hard part may therefore be the representation rather than the deque loop. Ask: what is the state, what are the legal transitions, and what exactly should count as one unit of cost?

13. Failure Modes Strong Learners Should Test

Using visited too early: a later zero-cost route may improve a previously discovered vertex.
Pushing to the wrong end: weight-0 edges belong at the front; weight-1 edges at the back.
Skipping relaxation: queue order does not remove the need to compare candidate distances.
Weights outside {0,1}: the deque ordering proof no longer applies.
Directed/undirected confusion: adding a reverse edge can change the problem completely.
Bad infinity value: fixed-width languages can overflow when adding to a sentinel that is too large.
Wrong parent update: update the predecessor only when the distance improves.
Premature early exit: exiting when a target is first discovered is not the same as exiting under a proved final-distance condition.
State compression mistakes: two states that look similar may have different future transition costs and cannot safely be merged.

14. Professional Engineering and Verification

A strong implementation should be checked against a trusted oracle. Generate random graphs with weights 0 and 1, run both 0–1 BFS and a conventional Dijkstra implementation, and compare every reachable distance. Differential testing catches subtle queue-order and relaxation mistakes quickly.

For large graphs, prefer compact integer vertex IDs and contiguous arrays when possible. Benchmark adjacency layouts rather than assuming one representation is fastest. If the algorithm sits in a latency-sensitive service, record graph size, edge density, number of relaxations, maximum deque size and runtime percentiles—not only average runtime.

15. Learning Progression: Beginner to Professional

Beginner: solve a five-vertex graph by hand and trace the deque after every relaxation.
Intermediate: implement distance and parent arrays, then reconstruct shortest paths.
Advanced: prove the deque ordering invariant and compare 0–1 BFS with heap-based Dijkstra on random graphs.
Professional: design 0/1 state graphs from real transition costs, build differential/property-based tests, profile representation overhead and establish safe early-exit conditions when needed.

16. Practice Problems

Trace the worked example and write the deque contents after each successful relaxation.
Construct a graph where marking a vertex visited on first discovery gives the wrong distance.
Convert a grid problem in which preferred moves cost 0 and other moves cost 1 into a graph.
Compare the number of heap operations in Dijkstra with deque operations in 0–1 BFS on the same random binary-weight graph.
Extend the Python implementation to support multiple sources at distance 0.
Build a differential test that checks 1,000 random graphs against Dijkstra.
Explain why replacing a weight 2 edge with the normal 0–1 BFS deque rule is invalid without transforming the graph or changing the algorithm.

17. Sources and Further Reading

Final idea: 0–1 BFS is a lesson in matching the data structure to the shape of the problem. The moment we notice that distances can advance only by zero or one, a general priority queue collapses into a deque. Good algorithm design often begins by finding exactly which generality the problem does not need.

Small Group Tutorials