Algorithm Deep Dive: 0-1 BFS & Bidirectional Search

A Bit of History

Standard Breadth-First Search (BFS) was introduced by Edward F. Moore in 1959 to find shortest paths in unweighted graphs. When edge weights are binary (e.g. $\{0, 1\}$ or $\{0, W\}$), competitive programmers and algorithm researchers realized that a double-ended queue (deque) maintains the monotonic distance property without needing an $O(\log V)$ priority queue.

Meanwhile, Ira Pohl introduced Bidirectional Search in 1969 ("Bi-directional Search in Path Finding Problems"). By launching two searches simultaneously — one forward from source $S$ and one backward from target $T$ — Pohl demonstrated that search space shrinks dramatically from $O(b^d)$ to $O(b^{d/2})$, where $b$ is the branching factor and $d$ is the path distance.

0-1 BFS: Double-Ended Queues

In standard BFS, a regular FIFO queue ensures vertices are popped in non-decreasing order of distance. If edge weights are restricted to $0$ and $W$ (commonly $0$ and $1$):

When relaxing edge $(u, v)$ with weight $w = 0$: $dist[v] = dist[u]$. Push $v$ to the FRONT of the deque.
When relaxing edge $(u, v)$ with weight $w = 1$: $dist[v] = dist[u] + 1$. Push $v$ to the BACK of the deque.

Why Does 0-1 BFS Work?

At any moment, the distances of nodes in the deque differ by at most 1 (i.e. all nodes in the deque have distance $k$ or $d + 1$). Pushing weight 0 nodes to the front ensures that all distance $k$ nodes are processed before any distance $k+1$ nodes!

Bidirectional Search

Standard single-source shortest path algorithms explore a ball of radius $d$ around source $S$, visiting $O(b^d)$ nodes. Bidirectional search explores two smaller balls of radius $d/2$ — one centered at $S$ and one centered at $T$:

$$b^{d/2} + b^{d/2} = 2 \cdot b^{d/2} \ll b^d$$

Bidirectional Search Frontiers

                            flowchart LR
                                S((Source S)) -->|Forward Frontiers| M((Meeting Node M))
                                T((Target T)) -->|Backward Frontiers| M
                                style S fill:#3B9797,stroke:#132440,color:#ffffff
                                style T fill:#BF092F,stroke:#132440,color:#ffffff
                                style M fill:#16476A,stroke:#132440,color:#ffffff

When searching with Dijkstra, the forward search maintains $dist_F[]$ and the backward search maintains $dist_B[]$. The algorithm terminates when a vertex $u$ is extracted from either priority queue that has been visited by both directional searches. The shortest path length is $\min_{v} \{ dist_F[v] + dist_B[v] \}$.

Worked Examples

0-1 BFS Trace

0-1 BFS on 4-Node Graph

Source node 0. Edges: (0-1, w=1), (0-2, w=0), (2-3, w=0), (2-1, w=0).

Init: dist[0]=0, deque=[0].
Pop front 0: relax (0,2,w=0) → dist[2]=0, push_front(2). Relax (0,1,w=1) → dist[1]=1, push_back(1). Deque: [2, 1].
Pop front 2: relax (2,3,w=0) → dist[3]=0, push_front(3). Relax (2,1,w=0) → dist[1]=0 (improved!), push_front(1). Deque: [1, 3, 1].
Pop front 1 (dist=0): node 1 final distance is 0!

Complexity Analysis

Algorithm	Time Complexity	Space Complexity	Primary Requirement
0-1 BFS	$O(V + E)$	$O(V)$	Edge weights $\in \{0, W\}$
Bidirectional BFS	$O(b^{d/2})$	$O(b^{d/2})$	Unweighted graph + known Target $T$
Bidirectional Dijkstra	$O(E \log V)$ (much smaller constant)	$O(V)$	Non-negative weights + known Target $T$

Implementations

from collections import deque
import heapq

def zero_one_bfs(n, adj, src):
    """0-1 BFS using collections.deque in O(V + E) time."""
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0

    dq = deque([src])

    while dq:
        u = dq.popleft()

        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)

    return dist

def bidirectional_dijkstra(n, adj, src, target):
    """Bidirectional Dijkstra algorithm returning shortest distance from src to target."""
    if src == target:
        return 0

    INF = float('inf')
    dist_F = [INF] * n
    dist_B = [INF] * n
    visited_F = [False] * n
    visited_B = [False] * n

    dist_F[src] = 0
    dist_B[target] = 0

    pq_F = [(0, src)]
    pq_B = [(0, target)]

    shortest = INF

    while pq_F and pq_B:
        # Step forward
        if pq_F:
            d_u, u = heapq.heappop(pq_F)
            if not visited_F[u]:
                visited_F[u] = True
                if visited_B[u]:
                    shortest = min(shortest, dist_F[u] + dist_B[u])
                for v, w in adj[u]:
                    if dist_F[u] + w < dist_F[v]:
                        dist_F[v] = dist_F[u] + w
                        heapq.heappush(pq_F, (dist_F[v], v))
                        if visited_B[v]:
                            shortest = min(shortest, dist_F[v] + dist_B[v])

        # Step backward
        if pq_B:
            d_u, u = heapq.heappop(pq_B)
            if not visited_B[u]:
                visited_B[u] = True
                if visited_F[u]:
                    shortest = min(shortest, dist_F[u] + dist_B[u])
                for v, w in adj[u]: # Assuming undirected or transpose for directed
                    if dist_B[u] + w < dist_B[v]:
                        dist_B[v] = dist_B[u] + w
                        heapq.heappush(pq_B, (dist_B[v], v))
                        if visited_F[v]:
                            shortest = min(shortest, dist_B[v] + dist_F[v])

        if pq_F and pq_B and (pq_F[0][0] + pq_B[0][0] >= shortest):
            break

    return shortest if shortest != INF else -1

# Testing
n = 5
adj = [[] for _ in range(n)]
edges = [(0, 1, 1), (0, 2, 0), (2, 3, 0), (2, 1, 0), (1, 4, 1), (3, 4, 1)]
for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))

print("0-1 BFS Distances from 0:", zero_one_bfs(n, adj, 0))
print("Bidirectional Dijkstra (0 to 4):", bidirectional_dijkstra(n, adj, 0, 4))

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 1e9;

vector<int> zeroOneBFS(int n, const vector<vector<pair<int, int>>>& adj, int src) {
    vector<int> dist(n, INF);
    dist[src] = 0;

    deque<int> dq;
    dq.push_back(src);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;

            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;
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> adj(n);
    vector<tuple<int, int, int>> edges = {
        {0, 1, 1}, {0, 2, 0}, {2, 3, 0}, {2, 1, 0}, {1, 4, 1}, {3, 4, 1}
    };
    for (auto& e : edges) {
        int u, v, w;
        tie(u, v, w) = e;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> dists = zeroOneBFS(n, adj, 0);
    cout << "0-1 BFS Distances: ";
    for (int d : dists) cout << d << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class ZeroOneBFS {
    static final int INF = 1_000_000_000;

    static class Edge {
        int v, w;
        Edge(int v, int w) { this.v = v; this.w = w; }
    }

    public static int[] solve(int n, List<List<Edge>> adj, int src) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;

        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.add(src);

        while (!dq.isEmpty()) {
            int u = dq.pollFirst();

            for (Edge e : adj.get(u)) {
                int v = e.v;
                int w = e.w;

                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (w == 0) {
                        dq.addFirst(v);
                    } else {
                        dq.addLast(v);
                    }
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Edge>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        int[][] edges = {{0,1,1}, {0,2,0}, {2,3,0}, {2,1,0}, {1,4,1}, {3,4,1}};
        for (int[] e : edges) {
            adj.get(e[0]).add(new Edge(e[1], e[2]));
            adj.get(e[1]).add(new Edge(e[0], e[2]));
        }

        int[] dists = solve(n, adj, 0);
        System.out.println("0-1 BFS Distances: " + Arrays.toString(dists));
    }
}

Real-World Applications

Case Study

Social Network Degree of Separation & Teleportation Grids

Finding the shortest connection path between two individuals on LinkedIn or Facebook uses **Bidirectional BFS**. Instead of searching millions of profiles in a 6-degree forward ball, searching simultaneously from both profiles intersects in a tiny fraction of the time. In game development, grid movement with zero-cost teleportation/warp gates relies on **0-1 BFS** to calculate optimal paths in $O(\text{Grid Size})$.

Social NetworksGame Development

Exercises

Prove that 0-1 BFS maintains a non-decreasing queue of distances.
Extend 0-1 BFS to handle edge weights $\{0, A, B\}$. Under what conditions does a deque suffice?
Why does Bidirectional Search require knowing the target node $T$ in advance?
Challenge: Write a Bidirectional A* Search algorithm combining landmark heuristics with forward and backward searches.

Limitations

Target Requirement & Weight Bounds

0-1 BFS cannot be applied when edge weights take on arbitrary integer values (use Dial's or Dijkstra's algorithm instead). Bidirectional search is single-pair only (source to target) and cannot be used for single-source all-destination queries.

Cookie Consent

0-1 BFS & Bidirectional Search

Contents

A Bit of History

0-1 BFS: Double-Ended Queues

Why Does 0-1 BFS Work?

Bidirectional Search

Worked Examples

0-1 BFS on 4-Node Graph

Complexity Analysis

Implementations

Real-World Applications

Social Network Degree of Separation & Teleportation Grids

Exercises

Limitations

Target Requirement & Weight Bounds

Cookie Consent

0-1 BFS & Bidirectional Search

Contents

A Bit of History

0-1 BFS: Double-Ended Queues

Why Does 0-1 BFS Work?

Bidirectional Search

Worked Examples

0-1 BFS on 4-Node Graph

Complexity Analysis

Implementations

Real-World Applications

Social Network Degree of Separation & Teleportation Grids

Exercises

Limitations

Target Requirement & Weight Bounds

Related Deep Dives

Graph Theory Series

Dial's Algorithm

A* Search & Heuristics