0-1 BFS

On an unweighted graph, BFS finds single-source shortest paths in O(|E|): distance is just the fewest edges. You can think of that as every edge having weight 1.

If weights are arbitrary, you need Dijkstra (O(|V|^2 + |E|) or O(|E| log |V|)).

If every weight is only 0 or 1, you can still solve SSSP in O(|E|) with a deque. That is 0-1 BFS.

Interactive deque

Same idea as the CPU pipeline stepper: Next walks one pop or one edge relax. Watch the deque stay sorted (d[v] then d[v]+1).

Why a deque is enough

Look at Dijkstra with a set as the priority queue:

d.assign(n, INF);
d[s] = 0;
set<pair<int, int>> q;
q.insert({0, s});
while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());

    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;
        if (d[v] + w < d[u]) {
            q.erase({d[u], u});
            d[u] = d[v] + w;
            q.insert({d[u], u});
        }
    }
}

In a 0-1 graph, vertices sitting in the queue never differ by more than 1 in distance from the source. If v is the current vertex, every u still in the queue satisfies

d[v] ≤ d[u] ≤ d[v] + 1

You only ever insert a vertex at the current distance or at current + 1. A vertex with d[u] - d[v] > 1 would have had to come from some t with d[t] > d[v], which Dijkstra would not process before v.

So the queue looks like:

Q =  [ v … u ]   [ m … n ]
       d[v]        d[v]+1

A balanced tree is overkill. Use a deque:

• Weight 0: new distance equals d[v] → push_front
• Weight 1: new distance equals d[v] + 1 → push_back

The deque stays sorted.

vector<int> d(n, INF);
d[s] = 0;
deque<int> q;
q.push_front(s);
while (!q.empty()) {
    int v = q.front();
    q.pop_front();
    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;
        if (d[v] + w < d[u]) {
            d[u] = d[v] + w;
            if (w == 1)
                q.push_back(u);
            else
                q.push_front(u);
        }
    }
}

Try a tiny graph

Edges: 0 --1--> 1, 1 --0--> 2, 0 --0--> 2. Distances from 0 should be 0, 1, 0.

🧪 0-1 BFS in C++

Check: 0-1 BFS

Quiz

0-1 BFS

1 / 4

0-1 BFS solves single-source shortest paths when…

Pick an answer to see if you are right.

Dial’s algorithm

If every edge weight is an integer ≤ k (not only 0/1), distances of vertices in the “queue” differ from d[v] by at most k. Keep k + 1 buckets. When the bucket for the smallest distance is empty, rotate to the next distance. That extension is Dial’s algorithm.

🧪 Dial’s buckets on weights ≤ 2

When to use it

Graph	Algorithm
Unweighted (or all weights 1)	Normal BFS
Weights only 0 and 1	0-1 BFS
Small integer weights 1 … k	Dial
Arbitrary non-negative weights	Dijkstra

Check: Dial & choice

Quiz

Dial and algorithm choice

1 / 4

Dial’s algorithm generalises 0-1 BFS when…

Pick an answer to see if you are right.

Exercises

Practice 0-1 BFS on classic grid problems. Open each link, solve on the judge, and map every move to a 0-cost or 1-cost edge.

B. Labyrinth

Judge: Codeforces 1063B — Labyrinth

You are in an n × m maze (. free, * obstacle). Start at row r, column c. You may move up, down, left, or right into free cells, staying in bounds.

Your keyboard is broken: you may move left at most x times and right at most y times. Up and down are unlimited.

How many cells (including the start) are reachable under those limits?

Constraints: 1 ≤ n, m ≤ 2000, 0 ≤ x, y ≤ 10⁹. The start cell is free.

Sample 1

Input
4 5
3 2
1 2
.....
.***.
...**
*....

Output
10

Reachable cells marked +:

+++..
+***.
+++**
*+++.

Sample 2

Input
4 4
2 2
0 1
....
..*.
....
....

Output
7

.++.
.+*.
.++.
.++.

Why 0-1 BFS?

Treat vertical moves as weight 0 and horizontal moves as weight 1. From the start, 0-1 BFS finds each cell with a minimum “horizontal budget”; then check whether that path fits within x left and y right (using the column difference). Naive BFS on (row, col, left, right) is too slow for n, m ≤ 2000.