0-1 BFS

When every edge weighs 0 or 1, shortest paths take $O(V+E)$ — no priority queue needed. Replace the queue with a deque: push 0-weight relaxations to the front, 1-weight relaxations to the back.

vector<int> zeroOneBFS(int n, int s, vector<vector<pair<int,int>>>& adj) {
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    deque<int> dq;
    dist[s] = 0;
    dq.push_front(s);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else        dq.push_back(v);
            }
    }
    return dist;
}

Why it works

The deque always contains at most two distinct distance values, $d$ and $d+1$, and they are ordered. Pushing a 0-weight neighbour to the front keeps it in the $d$ group; a 1-weight neighbour goes to the back, into the $d+1$ group. So the deque is always sorted by distance, which is exactly the invariant Dijkstra’s priority queue maintains — obtained here for free.

Each vertex can be pushed more than once, so add the stale check if (d > dist[u]) continue; if you also store distances in the deque, or simply allow the redundant pops: the total is still $O(E)$ because a vertex is only re-pushed when its distance strictly improves, and distances take at most $V$ distinct values.

When to reach for it

The trick fires whenever moves are naturally free or costly:

Problem	0-edge	1-edge
Grid where you may break walls	move into a free cell	break a wall
Minimum number of direction changes	continue straight	turn
Minimum edges to reverse to reach $t$	follow an edge forwards	traverse it backwards
Grid with portals / teleports	take a portal	take a normal step
Minimum characters to insert	match	insert
Connect all cells, some connections free	free link	paid link

The “minimum edge reversals” formulation is the one most worth memorising: build the graph with the original edges at cost 0 and their reverses at cost 1, then run 0-1 BFS.

Generalisations

Weights	Technique	Time
$\{0,1\}$	0-1 BFS (deque)	$O(V+E)$
$\{0,1,\dots ,k\}$ small	Dial’s algorithm — $kV+1$ buckets, sweep them in order	$O(kV+E)$
$\{0,w\}$ for one fixed $w$	rescale to $\{0,1\}$	$O(V+E)$
arbitrary non-negative	Dijkstra	$O(E\log V)$

Dial’s algorithm

// weights in [0, C]; distances are bounded by (V-1)*C
vector<vector<int>> bucket(V * C + 1);
bucket[0].push_back(s);
for (int d = 0; d <= V * C; d++)
    while (!bucket[d].empty()) {
        int u = bucket[d].back(); bucket[d].pop_back();
        if (dist[u] != d) continue;
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) { dist[v] = d + w; bucket[d + w].push_back(v); }
    }

Only worth it when $C$ is genuinely small — a bucket array of size $VC$ can be large.

See also: BFS · Dijkstra · Shortest Paths