Breadth-First Search: Multi-Source BFS, 0-1 BFS (Deque) & Bidirectional Search

The Two-Valued Queue Monotonicity Invariant

Why does a simple FIFO queue suffice to compute exact shortest paths in unweighted graphs, and why does a double-ended queue (deque) suffice when edge weights are $w(u, v) \in \{0, 1\}$? The answer lies in the Two-Valued Queue Invariant.

1. Multi-Source BFS via Virtual Super-Source

Given a set of source vertices $S = \{s_1, s_2, \dots, s_k\}$ (such as all exit cells in a grid or all infected nodes in a network), finding $\min_{s \in S} \text{dist}(s, v)$ for every vertex $v \in V$ does not require $k$ separate BFS runs. Conceptually, introduce a virtual super-source $s^*$ with directed zero-weight edges $(s^*, s_i)$ for all $s_i \in S$. In code, simply initialize $d[s_i] = 0$ and push all $s_i \in S$ into the queue at step 0 before starting the loop. Every vertex $v$ is visited at most once in $O(V + E)$ total time.

2. 0-1 BFS with a Double-Ended Queue (Dial's $C=1$ Specialization)

Many grid and state-space problems have free transitions ($w = 0$, e.g., moving along a conveyor belt's direction or staying in the same corridor) and unit-cost modifications ($w = 1$, e.g., rotating a tile or breaking a wall). Standard BFS fails because a path with more edges can have lower total weight. Dijkstra's algorithm runs in $O((V + E) \log V)$, whereas 0-1 BFS achieves $O(V + E)$:

• When relaxing $(u, v)$ with weight $w \in \{0, 1\}$, check if $d[u] + w < d[v]$.
• If improved, update $d[v] = d[u] + w$. If $w == 0$, call dq.push_front(v); if $w == 1$, call dq.push_back(v).
• Because a vertex $v$ might first be discovered via a weight-1 edge ($d[u] + 1$) and later relaxed via a weight-0 edge ($d[u'] + 0 = d[u]$), $v$ can be pushed into the deque at most twice. Popping a stale duplicate is skipped in $O(1)$ or guarded by a visited bitset upon pop.

3. Bidirectional BFS & Frontier Balancing

When searching for a shortest path between a single pair $(s, t)$ in a graph with branching factor $b$ and shortest-path distance $D$, standard BFS explores $\Theta(b^D)$ states. Bidirectional BFS maintains two frontiers $Q_f$ (expanding forward from $s$) and $Q_b$ (expanding backward along reversed edges from $t$). At each step, expand the frontier with fewer vertices ($|Q_f| \le |Q_b|$) by one full level. When the frontiers intersect at some vertex $m$, the shortest path has length $d_f[m] + d_b[m]$, and only $\Theta(2 \cdot b^{D/2})$ vertices are visited—turning $10^8$ states into $2 \times 10^4$.

Complexity Matrix

Production Implementation: 0-1 BFS & Multi-Source BFS

#include <vector>
#include <deque>
#include <limits>

struct Edge01 {
    int to;
    int weight; // Must be 0 or 1
};

std::vector<int> zeroOneBFS(int n, const std::vector<std::vector<Edge01>>& adj,
                            const std::vector<int>& sources) {
    constexpr int INF = std::numeric_limits<int>::max() / 2;
    std::vector<int> dist(n, INF);
    std::vector<uint8_t> settled(n, 0);
    std::deque<int> dq;

    for (int s : sources) {
        dist[s] = 0;
        dq.push_front(s);
    }

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        if (settled[u]) continue;
        settled[u] = 1;

        for (const auto& e : adj[u]) {
            if (dist[u] + e.weight < dist[e.to]) {
                dist[e.to] = dist[u] + e.weight;
                if (e.weight == 0) {
                    dq.push_front(e.to);
                } else {
                    dq.push_back(e.to);
                }
            }
        }
    }
    return dist;
}