0-1 BFS

Introduction

Breadth-First Search (BFS) is a standard algorithm for finding the shortest paths in an unweighted graph, where the distance is measured as the minimum number of edges traversed. This unweighted graph can be interpreted as a weighted graph with each edge having a weight of $1$ . For graphs with non-uniform edge weights, more general algorithms like Dijkstra's algorithm are typically used, which run in $O(|V|^2 + |E|)$ or $O(|E| \log |V|)$ time.

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

CODEFORCESLabyrinth

Rating: 1800

ATCODERE. Snuke's Subway Trip

CODEFORCESNastya and Unexpected Guest

Rating: 2400

∣

log

∣

)

However, when the edge weights are limited to either $0$ or $1$ , we can optimize the solution to $O(|E|)$ time.

Key Idea

Understanding the 0-1 BFS algorithm involves analyzing Dijkstra's algorithm under the constraint that each edge weight is either $0$ or $1$ . In Dijkstra's algorithm, the distances between the source and other vertices in the priority queue differ by at most one. This implies that for any vertex $u$ in the queue, $d[v] \le d[u] \le d[v] + 1$ .

Given this property, if there were a vertex $u$ in the queue with $d[u] - d[v] > 1$ , it would have been inserted via a different vertex $t$ where $d[t] \ge d[u] - 1 > d[v]$ . However, this is impossible as Dijkstra's algorithm processes vertices in increasing distance order.

Therefore, the queue in 0-1 BFS can be maintained as:

$Q = \underbrace{v}_{d[v]}, \dots, \underbrace{u}_{d[v]}, \underbrace{m}_{d[v]+1}, \dots, \underbrace{n}_{d[v]+1}$

This simpler structure allows us to use a deque instead of a priority queue. Vertices are added to the front of the deque if the corresponding edge has weight $0$ , or to the back if the edge has weight $1$ . This approach ensures the deque remains sorted.

Algorithm Steps

0-1 BFS uses a double-ended queue (deque) to manage vertices during traversal.

Initialize all vertex distances as infinite, except for the source vertex which is set to 0. Add the source vertex to the deque.
While the deque is not empty:
- Dequeue a vertex $u$ from the front.
- For each adjacent vertex $v$ of $u$ :
  - If the edge $u-v$ has weight 0 and visiting $v$ minimizes its distance, enqueue $v$ at the front of the deque.
  - If the edge $u-v$ has weight 1 and visiting $v$ minimizes its distance, enqueue $v$ at the back of the deque.

Implementation

The implementation of 0-1 BFS in C++ using a deque is as follows:

vector<int> d(n, INF);
// s is the source vertex.
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);
        }
    }
}