0-1 BFS

0-1 BFS finds the shortest distance from one vertex to every other vertex in a graph where each edge weighs 0 or 1, such as a map where some moves are free and others cost one step. If every edge weighs 1, plain BFS is enough; if the weights can be 2 or more, use Dijkstra's algorithm.

Explanation

Six towns are joined by five roads. Two are free, and on the other three, the toll roads, you pay one coin. How many coins does it take to drive from town 1 to each town? There is only one route to each town, so count its toll roads. The answers spread out from town 1 in waves: a wave runs along free roads at once and stops at toll roads, and each toll road starts the next wave.

Fig. 1. Each town shows the fewest coins from town 1. Town 2 joins town 1's wave over the free road; town 6 is two toll roads away.

Real road maps have loops. Here is a map with 8 towns and 9 roads, and we look for the fewest coins from town 1 to town 5.

Fig. 2. Red: 2 coins. Blue: 1 coin.

Town 5 can be reached in several ways. The red route goes straight through town 2: two roads, both toll roads, so 2 coins. The blue route goes round through towns 3, 4 and 2: four roads, but only the last one is a toll road, so 1 coin.

The first thing to try is BFS: spread out from town 1, take towns in the order they were found, and keep the first number each town gets. Town 1 finds town 2 over a toll road (1) and town 3 over a free road (0). Town 2 is the oldest in the line, so it is taken next, and it gives town 5 the number 1 + 1 = 2. The blue route turns up later, but by then town 2 and town 5 already have their numbers. The result for town 5 is 2, along the red route, while the true answer is 1. Town 4 comes out wrong too: 1 instead of 0.

Dijkstra's algorithm would find 1, but on a map with a million roads each step of its priority queue takes about 20 comparisons, where a plain line takes one.

Town 3 was found at the same moment as town 2, but it costs nothing to get there, and nothing more to go on from it over free roads. So it should not wait behind town 2. A town reached over a free road goes to the front of the line, and a town reached over a toll road goes to the back, as in BFS. Then the line stays in order: the towns at the front have the same number as the town just taken, and the towns at the back have one more.

Town 2 got its first number the expensive way, so that number can still drop. Keep the smallest number found so far, as in Dijkstra's algorithm. When a town's number drops, put the town in the line again, and process each town only the first time it is taken. On our map, town 5 then gets 1, along the blue route.

A line you can add to and take from at both ends is a deque, and this algorithm is 0-1 BFS: breadth-first search on a deque. It takes towns in the same order as Dijkstra's algorithm, without a priority queue.

Town 1 gets 0 and is the only entry in the deque.

Town 1 is taken from the front of the deque and processed. Its number 0 is final.

The toll road from town 1 gives town 2 the number 0 + 1 = 1, and town 2 joins the back of the deque.

The free road from town 1 gives town 3 the number 0 + 0 = 0, and town 3 joins the front of the deque.

Town 3 is taken from the front of the deque and processed. Its number 0 is final.

The free road from town 3 gives town 4 the number 0 + 0 = 0, and town 4 joins the front of the deque.

Town 4 is taken from the front of the deque and processed. Its number 0 is final.

The free road from town 4 lowers town 2 from 1 to 0 + 0 = 0, and town 2 joins the front of the deque again.

The toll road from town 4 gives town 6 the number 0 + 1 = 1, and town 6 joins the back of the deque.

Town 2 is taken from the front of the deque and processed. Its number 0 is final.

The toll road from town 2 gives town 5 the number 0 + 1 = 1, and town 5 joins the back of the deque.

The entry 2:1 at the front is stale: town 2 is already processed, so it is skipped.

Town 6 is taken from the front of the deque and processed. Its number 1 is final.

The toll road from town 6 gives town 7 the number 1 + 1 = 2, and town 7 joins the back of the deque.

Town 5 is taken from the front of the deque and processed. Its number 1 is final.

The free road from town 5 lowers town 7 from 2 to 1 + 0 = 1, and town 7 joins the front of the deque again.

Town 7 is taken from the front of the deque and processed. Its number 1 is final.

The toll road from town 7 gives town 8 the number 1 + 1 = 2, and town 8 joins the back of the deque.

The entry 7:2 at the front is stale: town 7 is already processed, so it is skipped.

Town 8 is taken from the front of the deque and processed. Its number 2 is final.

The deque is empty. Towns 1 to 8 have 0 0 0 0 1 1 1 2.

1/21

Fig. 3. Step through 0-1 BFS on the 8-town map. Green towns are processed and their numbers are final. The boxes below are the deque, front on the left; a struck-out box is a stale entry.

The fewest coins from town 1 to town 5 is 1. The same run gives the answer for every town, in waves as on the small map: towns 1 to 4 with 0, then towns 5, 6 and 7 with 1, then town 8 with 2.

Breaking walls

The same waves solve a maze where you may break through walls. Walking into an open cell is free, and breaking into a wall cell costs 1. What is the fewest walls to break on the way from the top-left corner S to the bottom-right corner E? Without breaking walls, E can't be reached at all. The open cells that can be reached from S without breaking anything get 0, and each wall broken starts the next wave. E gets 2, so the answer is 2.

Fig. 4. Each cell shows the fewest walls broken to reach it. Grey cells are walls.

Implementation

In code we say vertex and edge: a town is a vertex, a road is an edge, and a free road weighs 0 and a toll road 1. The start vertex is s. As in Dijkstra's algorithm, d[v] is the smallest number found so far for vertex v. Once a vertex is processed, its d[v] is final.

For a start vertex s, the algorithm is:

1. Initialise: d[s] = 0, every other d[v] is INF, and the deque holds s.

2. Take the next vertex v from the front. If v is already processed, this is a stale entry, left from before d[v] dropped: skip it.

3. Mark v processed.

4. Relax every edge v–u of weight w: if d[v] + w < d[u], set d[u] = d[v] + w and push u, to the front for w == 0 and to the back for w == 1.

5. Stop when the deque is empty; otherwise repeat from step 2.

The program reads n and m, then m lines u v w: a two-way road between u and v with weight w, which is 0 or 1. Vertices are numbered from 1 to n, and the start is vertex 1. The program prints the distance to each vertex, or -1 for a vertex that can't be reached. Then it prints a cheapest route from vertex 1 to a target t, using parent[u]: the vertex whose edge last lowered d[u]. Walking back along parent from t ends at vertex 1, where parent[1] = 0. For the 8-town map the input is:

8 9
1 2 1
1 3 0
3 4 0
2 4 0
2 5 1
4 6 1
5 7 0
6 7 1
7 8 1

The graph is stored as an adjacency list of (neighbour, weight) pairs, and std::deque gives push_front, push_back, front and pop_front. The comments name the steps above.

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});   // remove this line if the roads are one-way
    }

    const int INF = 99;   // small for the demo; use 1e9 for real inputs
    int s = 1;
    vector<int> d(n + 1, INF);
    vector<int> parent(n + 1, 0);   // only needed to print the route
    vector<bool> processed(n + 1, false);
    deque<int> dq;

    // initialise
    d[s] = 0;
    dq.push_back(s);

    while (!dq.empty()) {              // stop: when the deque is empty
        // take the next vertex
        int v = dq.front();
        dq.pop_front();
        if (processed[v]) continue;    // stale entry

        // mark it
        processed[v] = true;

        // relax its edges
        for (auto [u, w] : adj[v]) {
            if (d[v] + w < d[u]) {
                d[u] = d[v] + w;
                parent[u] = v;   // only needed to print the route
                if (w == 0) dq.push_front(u);
                else dq.push_back(u);
            }
        }
    }

    for (int v = 1; v <= n; v++) {
        cout << (d[v] == INF ? -1 : d[v]) << (v < n ? ' ' : '\n');
    }

    // print a cheapest route from s to t; remove this block if you only need distances
    int t = 5;
    if (d[t] != INF) {
        vector<int> route;
        for (int v = t; v != 0; v = parent[v]) route.push_back(v);
        reverse(route.begin(), route.end());
        for (int v : route) cout << v << ' ';
        cout << '\n';
    }
}

A distance is at most n - 1, so int is enough. The skip line is not needed for the answer: a stale entry would relax its edges again and change nothing. It saves that repeated work. For t = 5 the program prints the route 1 3 4 2 5, the blue route of Fig. 2.

A vertex first gets $k$ or k + 1 while the front of the deque has $k$, and its true distance is at least $k$, so d[v] drops at most once and each vertex is pushed at most twice. Each edge is relaxed once from each end, so the time and memory are O(n + m), against O((n + m) \log m) for Dijkstra's algorithm.

Grids

On a grid the vertices are cells, and the weight of a move depends on the cell you enter. For the maze in Fig. 4, a move into a wall costs 1 and a move into an open cell costs 0. The program reads the grid into g, a vector of R strings of length C, and defines INF as before; the start is at row sr, column sc. On the Fig. 4 maze, d[4][4] ends as 2.

int dr[] = {-1, 1, 0, 0};   // up, down, left, right
int dc[] = {0, 0, -1, 1};

// initialise
vector<vector<int>> d(R, vector<int>(C, INF));
vector<vector<bool>> processed(R, vector<bool>(C, false));
deque<pair<int, int>> dq;
d[sr][sc] = 0;
dq.push_back({sr, sc});

while (!dq.empty()) {
    // take the next vertex
    auto [r, c] = dq.front();
    dq.pop_front();
    if (processed[r][c]) continue;    // stale entry

    // mark it
    processed[r][c] = true;

    // relax its edges
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;  // outside the grid
        int w = (g[nr][nc] == '#') ? 1 : 0;                    // breaking a wall costs 1
        if (d[r][c] + w < d[nr][nc]) {
            d[nr][nc] = d[r][c] + w;
            if (w == 0) dq.push_front({nr, nc});
            else dq.push_back({nr, nc});
        }
    }
}

Several starts

To find the distance to the nearest of several start vertices, set d[s] = 0 for each start s and push them all before the loop, as in multi-source BFS. Sometimes a start already costs 1, as on a grid where you may enter at any border cell and a border wall must be broken first. Give such a start d[s] = 1 and push it to the back after all the starts with 0, so the deque begins with a block of 0 and then a block of 1, as the invariant in the proof needs.

Correctness proof

Each entry carries the value d_u had when it was pushed. The algorithm keeps this invariant: the deque holds entries with some value $k$ at the front, then entries with k + 1 behind them, and nothing else. These two blocks are the current wave and the next one.

At the start the deque holds only $s$ with 0. Suppose the invariant holds and the front entry, with $k$, is taken. A 0-edge gives a neighbour $k$, and it joins the front, next to the other $k$ entries. A 1-edge gives k + 1, and it joins the back, behind the other k + 1 entries. Stale entries change nothing. When the last $k$ entry is gone, the k + 1 block becomes the front, and new entries get k + 1 or k + 2. So the invariant holds after every step, and the front entry always has the smallest value in the deque.

Fig. 5. The moment after town 4 is taken: the value k = 0 at the front, then the values k + 1 = 1 behind the bar.

That is the entry Dijkstra's priority queue would give out. Vertices are taken in the same order of distance as in Dijkstra's algorithm, with the same relaxations, so Dijkstra's proof carries over unchanged: when a vertex is taken for the first time, its d_v is its true distance.

Other weights

The invariant needs every weight to be 0 or 1. Take an edge of weight 2 and push it to the back: now an entry with k + 2 can sit in front of a later entry with k + 1, and the front is no longer the smallest.

Here is 0-1 BFS from vertex 1 on a small undirected graph with one edge of weight 2.

Vertex 1 gets 0 and is the only entry in the deque.

Vertex 1 is taken from the front of the deque and processed with 0.

The edge of weight 2 from vertex 1 gives vertex 2 the value 0 + 2 = 2, and vertex 2 joins the back of the deque.

The edge of weight 1 from vertex 1 gives vertex 3 the value 0 + 1 = 1, and vertex 3 joins the back of the deque. Now 2:2 sits in front of 3:1, a smaller value.

Vertex 2 is taken from the front of the deque and processed with 2.

The edge from vertex 2 to vertex 1 gives 2 + 2 = 4, no better than 0. Nothing changes.

The edge from vertex 2 to vertex 3 gives 2 + 0 = 2, no better than 1. Nothing changes.

The edge of weight 1 from vertex 2 gives vertex 4 the value 2 + 1 = 3, and vertex 4 joins the back of the deque.

Vertex 3 is taken from the front of the deque and processed with 1.

The edge from vertex 3 to vertex 1 gives 1 + 1 = 2, no better than 0. Nothing changes.

The edge of weight 0 from vertex 3 lowers vertex 2 from 2 to 1 + 0 = 1, and vertex 2 joins the front of the deque. But vertex 2 is already processed, so vertex 4 keeps 3.

The entry 2:1 at the front is stale: vertex 2 is already processed, so it is skipped.

Vertex 4 is taken from the front of the deque and processed with 3.

The edge from vertex 4 to vertex 2 gives 3 + 1 = 4, no better than 1. Nothing changes.

The deque is empty. The run gives 0 1 1 3, but the true distance of vertex 4 is 2.

1/15

Fig. 6. The weight-2 entry sits in front of a smaller value, so vertex 2 is processed too early and vertex 4 keeps 3.

For such weights use Dijkstra's algorithm, or split each 2-edge into two 1-edges through a new vertex.

Common mistakes

• Keeping the first d_u a vertex gets, as in BFS, although a vertex pushed with k + 1 over a 1-edge can still drop to $k$ over a 0-edge. Relax with d[v] + w < d[u] and mark a vertex processed when it is taken.

• Using a plain queue, with every vertex pushed to the back. A vertex is then taken before a free route lowers its distance, so either the answer is wrong or, without the processed check, vertices are processed again and the time grows to $O(nm)$; push 0-edges to the front.

• Swapping the ends, 0-edges to the back and 1-edges to the front, which breaks the order of the deque and gives wrong distances. Push 0-edges to the front and 1-edges to the back.

Similar algorithms

BFS is the special case where every edge weighs 1.

Dijkstra's algorithm also solves 0/1 graphs, in O((n + m) \log m).

Multi-source BFS starts from several vertices at once; see "Several starts" above.

Problems often hide 0/1 costs in the moves of a state graph: for example, the state is (cell, direction), four states per cell, going straight is free, and turning costs 1. Reversing an edge, breaking a wall or rotating a tile are other moves that cost 1.

Practice