0-1 BFS

0-1 BFS is the trick that finds shortest paths on a graph whose edges cost only 0 or 1 — in linear time, no priority queue needed. It is a beautiful upgrade to plain BFS, and a favorite for graphs where some moves are "free."

The slow way first

The general tool for weighted shortest paths is Dijkstra, which uses a priority queue (a heap). That works, but it costs O(E log V) because every push and pop touches the heap.

The question to ask: do I really need a full priority queue? With arbitrary weights, yes. But when every weight is only 0 or 1, the set of "live" distances at any moment spans at most two values — some distance d and d + 1. That tiny range means we can replace the heap with something much cheaper.

The idea: a deque instead of a heap

Run a BFS, but use a double-ended queue (deque). When you relax an edge out of vertex u:

• weight 0 → the neighbor has the same distance as u, so push it to the front.
• weight 1 → the neighbor is one farther, so push it to the back.

This keeps the deque sorted by distance at all times, just like a heap would — but with O(1) pushes and pops. The first time a vertex is popped, its distance is final.

The key insight: because the deque never holds more than two distinct distance values, "front" always means the smallest distance — so a deque gives the same ordering guarantee as a heap, for free.

Walk through it

Step through the animation. We start at S with distance 0. Popping S, the edge S→B is weight 0 so B jumps to the front at distance 0; S→A is weight 1 so A goes to the back at distance 1. Watch the deque stay ordered: when we later relax A→C (weight 0), C slips ahead of T even though T was queued earlier. The first pop of each vertex locks in its final distance.

Pseudocode

dist[source] = 0, all others = infinity
deque dq = [source]
while dq is not empty:
    u = pop from FRONT
    for each edge (u -> v) with weight w:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if w == 0: push v to the FRONT
            else:      push v to the BACK
return dist

The Python solution

from collections import deque
 
def zero_one_bfs(graph, source, n):
    dist = [float("inf")] * n
    dist[source] = 0
    dq = deque([source])
    while dq:
        u = dq.popleft()
        d = dist[u]
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

• dist starts as all infinity except the source, which is 0.
• dq is a deque seeded with the source. We always pop from the front with popleft.
• For each neighbor v with edge weight w, the candidate distance is nd = d + w.
• We only act when nd < dist[v] — the standard relaxation check.
• Lines 14-18 are the heart of it: a 0-weight edge does appendleft (front), a 1-weight edge does append (back). That single choice keeps the deque sorted by distance.

Complexity

Each vertex can be pushed a few times, but every edge is relaxed a constant number of times, so the total work is linear in the size of the graph. That is strictly faster than Dijkstra — the 0/1 weight restriction buys us the log factor.

When this pattern shows up

Practice