Why this matters
Some route problems have only two kinds of cost. A road is either free or costs one unit. A tile in a maze is either open for free or needs one unit of effort to break through. A switch either keeps its state or costs one press to flip. Problems like these come up in interviews and in real systems that route traffic or plan moves.
The usual tool for shortest paths is Dijkstra's algorithm. It works for any non-negative cost, but it keeps a priority queue (a container that always gives back the smallest item), and each insert and remove costs time that grows with the logarithm of the queue size. When every cost is 0 or 1, there is a simpler method. It uses a plain double-ended queue (a deque, which lets you add and remove at both ends in constant time) and it runs in time proportional to the number of nodes plus the number of edges.
This lesson builds that method in C++ with std::deque. It assumes you know plain breadth-first search (BFS), which visits nodes in rings around the start and uses a queue. If that is new, read the grid flood fill lesson earlier in this module first. Here we only need one idea from it: a queue hands out nodes in the order they were added.
Start with the problem, not the code
Plain BFS finds the path with the fewest edges. It does not find the path with the lowest total cost. The difference matters as soon as edges have different costs.
Take a small town with four places: A, B, C and D. Here are the roads.
- A road from
AtoBcosts 1 unit of time. - A road from
AtoCcosts 0 units, because it is a free ferry. - A road from
CtoBcosts 0 units, because it is also a free ferry. - A road from
BtoDcosts 1 unit.
We want the cheapest time from A to B. Plain BFS looks at the roads out of A and sees B directly. It says the cost is 1. But going A to C to B costs 0 + 0 = 0, which is cheaper. Plain BFS did not look for the cheapest route. It looked for the route with the fewest roads.
There are two correct tools here. Dijkstra's algorithm handles this case, and so does 0-1 BFS, which is the subject of this lesson. The 0-1 BFS version is shorter and faster when every cost is 0 or 1. It stays correct only in that case, so check the costs before you use it.
The analogy: a line that is kept in order
Picture people standing in a line at a ticket counter. The line is sorted by how much time each person has already spent getting there. The person at the front has spent the least time. The person at the back has spent the most.
When you serve the person at the front, you look at who they can reach next.
- If the next place is free to reach, the new person has spent exactly the same time. They step to the front of the line, because they are just as early as the person you just served.
- If the next place costs one unit, the new person has spent one more unit than the person you just served. They join the back of the line.
The line stays sorted. Nobody has to move in the middle of the line, and nobody has to search for the right position. That is the whole idea. A deque is the right container because it gives you a cheap way to add at the front and at the back.
Vocabulary before code
- Graph: a set of nodes (points) joined by edges (links). A road map is a graph where places are nodes and roads are edges.
- Directed edge: an edge that goes one way, from one node to another. A one-way street is a directed edge.
- Cost or weight: a number attached to an edge. In this lesson it is always 0 or 1.
- Distance: the lowest total cost from the start node to another node. It is the sum of the edge costs along the cheapest path.
- Deque: a double-ended queue. You can add or remove at the front or at the back. In C++ it is
std::deque, and the methods arepush_front,push_back,pop_front, andfront. - Relax: to try a new, cheaper distance for a node through an edge. If the new distance is lower than the stored one, you store it.
- Stale entry: a copy of a node in the deque that holds an old distance. A node can be in the deque more than once. The older copy is stale.
We also use adjacency list. It is a list, one per node, of the edges that leave that node. In C++ it is a std::vector of std::vector of edges. Each edge stores where it goes and what it costs.
Representing the graph in C++
Each edge is a destination and a cost. We pack them into a small struct.
struct Edge {
int to; // the node this edge goes to
int cost; // 0 or 1
};
using Graph = std::vector<std::vector<Edge>>;Graph graph(5) makes five nodes, numbered 0 to 4, with no edges yet. To add a directed edge from node 0 to node 1 with cost 1, you write graph[0].push_back({1, 1});. Node numbers start at 0 because they are indexes into the vector.
The algorithm in plain steps
- Create a distance for every node. Start with "infinity", meaning not reached yet. Set the start node's distance to 0.
- Put the start node in the deque.
- While the deque is not empty, take the node at the front and call it
node. - Look at each edge leaving
node. Letcandidatebedist[node]plus the edge cost. - If
candidateis smaller than the stored distance of the other end, store it. Then push the other end to the front if the cost is 0, or to the back if the cost is 1. - When the deque is empty, every reachable node has its final distance.
That is all of it. The only special part is step 5: the choice between front and back.
The code
Here is the complete function. It returns the distance from a start node to every node, and uses -1 for nodes that cannot be reached.
#include <deque>
#include <limits>
#include <vector>
struct Edge {
int to;
int cost; // must be 0 or 1
};
using Graph = std::vector<std::vector<Edge>>;
std::vector<int> zeroOneBfs(const Graph& graph, int source) {
constexpr int kInf = std::numeric_limits<int>::max();
std::vector<int> dist(graph.size(), kInf);
std::deque<int> queue;
dist[source] = 0;
queue.push_back(source);
while (!queue.empty()) {
int node = queue.front();
queue.pop_front();
for (const Edge& edge : graph[node]) {
int candidate = dist[node] + edge.cost;
if (candidate < dist[edge.to]) {
dist[edge.to] = candidate;
if (edge.cost == 0) {
queue.push_front(edge.to);
} else {
queue.push_back(edge.to);
}
}
}
}
for (int& d : dist) {
if (d == kInf) d = -1;
}
return dist;
}Two details matter. First, the code only relaxes when candidate is strictly smaller. A node that already has a distance equal to or below candidate is left alone. Second, dist[node] is never kInf when node is in the deque, so the addition on the candidate line never overflows. Only nodes that have been reached are pushed, and they always have a real distance.
Worked example 1: a small graph, traced step by step
Here is a graph with five nodes. The edges are written as from -> to (cost).
0 -> 1 (cost 1)0 -> 2 (cost 0)2 -> 1 (cost 0)2 -> 3 (cost 1)1 -> 3 (cost 1)1 -> 4 (cost 1)3 -> 4 (cost 0)
We start at node 0. The program below prints the deque after each step. The number in brackets is the distance stored when that node was pushed.
#include <deque>
#include <iostream>
#include <limits>
#include <vector>
struct Edge { int to; int cost; };
int main() {
constexpr int kInf = std::numeric_limits<int>::max();
std::vector<std::vector<Edge>> g(5);
g[0] = {{1, 1}, {2, 0}};
g[2] = {{1, 0}, {3, 1}};
g[1] = {{3, 1}, {4, 1}};
g[3] = {{4, 0}};
std::vector<int> dist(5, kInf);
std::deque<int> q;
dist[0] = 0;
q.push_back(0);
auto show = [&](const char* label) {
std::cout << label << " deque:";
for (int x : q) std::cout << ' ' << x << "(" << dist[x] << ")";
std::cout << " dist:";
for (int d : dist) std::cout << ' ' << (d == kInf ? -1 : d);
std::cout << '\n';
};
show("start");
while (!q.empty()) {
int u = q.front();
q.pop_front();
std::cout << "pop " << u << " (dist " << dist[u] << ")\n";
for (auto [v, c] : g[u]) {
if (dist[u] + c < dist[v]) {
dist[v] = dist[u] + c;
if (c == 0) q.push_front(v); else q.push_back(v);
std::cout << " relax " << u << "->" << v << " cost " << c
<< " to " << dist[v] << (c == 0 ? " push_front" : " push_back") << '\n';
}
}
show(" state");
}
std::cout << "final dist:";
for (int d : dist) std::cout << ' ' << d;
std::cout << '\n';
}Compiled with g++ -std=c++20 -Wall (g++ 15.2.0 on Linux), the output is:
start deque: 0(0) dist: 0 -1 -1 -1 -1
pop 0 (dist 0)
relax 0->1 cost 1 to 1 push_back
relax 0->2 cost 0 to 0 push_front
state deque: 2(0) 1(1) dist: 0 1 0 -1 -1
pop 2 (dist 0)
relax 2->1 cost 0 to 0 push_front
relax 2->3 cost 1 to 1 push_back
state deque: 1(0) 1(0) 3(1) dist: 0 0 0 1 -1
pop 1 (dist 0)
relax 1->4 cost 1 to 1 push_back
state deque: 1(0) 3(1) 4(1) dist: 0 0 0 1 1
pop 1 (dist 0)
state deque: 3(1) 4(1) dist: 0 0 0 1 1
pop 3 (dist 1)
state deque: 4(1) dist: 0 0 0 1 1
pop 4 (dist 1)
state deque: dist: 0 0 0 1 1
final dist: 0 0 0 1 1Read the trace carefully, because it shows every rule at work.
- The first pop is node 0 with distance 0. Its edge to node 2 costs 0, so node 2 goes to the front. Its edge to node 1 costs 1, so node 1 goes to the back. The deque is now
2, 1. - Node 2 is popped next. Its edge to node 1 costs 0. The candidate distance for node 1 is 0, which beats the stored 1. Node 1 is pushed to the front, so the deque is
1, 1, 3. Node 1 is now in the deque twice. The first copy holds the new distance 0. The second copy was pushed earlier at distance 1, but the stored distance has already dropped to 0. It is stale. - The first copy of node 1 is popped and relaxes node 4 with cost 1. Node 4 gets distance 1 and goes to the back.
- The second copy of node 1 is popped. Its stored distance is 0, so it tries the same edges again. Nothing improves, so nothing is pushed. This is the cost of stale entries: a little extra work, no wrong answer.
- Nodes 3 and 4 are popped with distance 1. Nothing else changes.
The final answer is 0 0 0 1 1. The distance to node 3 is 1, not 2. The cheapest path goes 0 -> 2 -> 3, and it costs 0 + 1 = 1. Plain BFS would have said 2, because 0 -> 1 -> 3 has two edges.
Notice the order of the deque in every line of the trace. The distances always read in non-decreasing order from front to back: 0, 0, 1, then 0, 1, 1. That is the invariant the proof depends on.
Why the order stays right: the proof
We need two claims. First, when a node is popped for the first time, its distance is final. Second, each node enters the deque at most twice, so the work stays small.
We write value for the distance a node had at the moment it was pushed. Each entry in the deque has a value.
Claim 1. The values in the deque never decrease from front to back, and the front value and the back value differ by at most 1.
Look at the start. The deque holds one entry with value 0. The claim holds.
Now assume the claim is true, and take one step. Let d be the value of the front entry. Because the values are sorted and the back is at most d + 1, every value in the deque is either d or d + 1. We pop the front, which has value d. The entries that are left still have values d or d + 1. When we pop a node, we relax its edges, and a new entry is added in one of two ways.
- A cost 0 edge gives candidate
d + 0 = d. The new entry has valuedand goes to the front. Every value in the deque is at leastd, so the front is still the smallest. The back is at mostd + 1, so the spread is still at most 1. - A cost 1 edge gives candidate
d + 1. The new entry has valued + 1and goes to the back. Every value in the deque is at mostd + 1, so the back is still the largest. The front is at leastd, so the spread is still at most 1.
So the claim holds after every step.
Claim 2. A node is pushed at most twice.
When we pop a node at level d, its neighbours can only receive candidates of d or d + 1. A node stored at d cannot improve, because nothing lower than d can be produced. A node stored at d + 1 can improve once, to d. After that it cannot change again. A node that was never reached is pushed for the first time with value d or d + 1. So each node has at most two pushes.
I checked this on 2,000 random graphs with 0 and 1 costs. The largest number of pushes for any node was 2, as the proof predicts.
Claim 3. When a node is popped for the first time, its distance is final.
This is the same reason Dijkstra's algorithm works. Values leave the deque in non-decreasing order, because the front always holds the smallest value. Suppose a shorter path to a node v existed, with total cost below the value d that v has when it is popped. Walk that shorter path from the start. Its last step into a not-yet-finished node would carry a value below d, and such a value must already have left the deque before v. So that node was finished, and its neighbour on the path would have been relaxed and pushed before v was popped. That contradicts the assumption, so d is final.
Together these claims show that the method is correct and that it runs in time proportional to the number of nodes plus the number of edges. Each node is popped at most twice, and each pop scans that node's edges once. Stale pops scan edges again, but there are at most two copies per node, so the total work is at most about twice the number of edges plus the number of nodes.
Worked example 2: a grid where walls cost 1
A grid is a common place to see 0-1 costs. Imagine a map where each square is either open (.) or a wall (#). You may walk through open squares for free. Walking into a wall means breaking it, and that costs 1. The question is: what is the fewest walls you must break to go from the top left corner to the bottom right corner?
Each square is a node. You can move up, down, left or right, so each square has up to four edges. The cost of an edge is 0 if the square you enter is open, and 1 if it is a wall. Costs are only 0 or 1, so 0-1 BFS applies.
#include <deque>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
int minWallsBroken(const std::vector<std::string>& grid) {
const int rows = static_cast<int>(grid.size());
const int cols = static_cast<int>(grid[0].size());
constexpr int kInf = std::numeric_limits<int>::max();
std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, kInf));
std::deque<std::pair<int, int>> queue;
dist[0][0] = 0;
queue.push_back({0, 0});
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};
while (!queue.empty()) {
auto [r, c] = queue.front();
queue.pop_front();
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
int cost = (grid[nr][nc] == '#') ? 1 : 0;
int candidate = dist[r][c] + cost;
if (candidate < dist[nr][nc]) {
dist[nr][nc] = candidate;
if (cost == 0) {
queue.push_front({nr, nc});
} else {
queue.push_back({nr, nc});
}
}
}
}
return dist[rows - 1][cols - 1];
}
int main() {
std::vector<std::string> grid = {
"..#..",
"#.#.#",
"..#..",
"#..#.",
"..#..",
};
std::cout << "walls broken: " << minWallsBroken(grid) << '\n';
std::vector<std::string> open = {"...", "...", "..."};
std::cout << "open grid: " << minWallsBroken(open) << '\n';
std::vector<std::string> walled = {"..#", "###", "#.."};
std::cout << "walled grid: " << minWallsBroken(walled) << '\n';
}The output is:
walls broken: 1
open grid: 0
walled grid: 1Check the first answer by hand. From the top left, the open squares reach a dead end. Breaking one wall gets past the middle column. Breaking the wall at row 0, column 2 works, and so does the wall at row 2, column 2. Either way the answer is 1. The third grid has one full row of walls. You break one wall in it to pass through, so the answer is 1 again.
Notice what the code does not do. It does not check whether the target is reachable at all. In this problem every wall can be broken, so the target is always reachable and the answer is always a number. If your problem can have cut-off squares, dist stays at infinity for the target, and you must test for that.
Worked example 3: reversing one-way edges
Now a harder case. A set of one-way roads is given. You are at node 0 and want to reach node 4. You may reverse any one-way road, but reversing one costs 1. What is the fewest reversals needed?
The trick is to treat each road in two directions. Following the road the right way costs 0. Following it backwards costs 1, because it means reversing the road. We add both kinds of arc to the graph, then run 0-1 BFS as before.
#include <deque>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
int minReversals(int n, const std::vector<std::pair<int, int>>& roads, int from, int to) {
constexpr int kInf = std::numeric_limits<int>::max();
struct Arc { int to; int cost; };
std::vector<std::vector<Arc>> g(n);
for (auto [u, v] : roads) {
g[u].push_back({v, 0}); // follow the road as it is: free
g[v].push_back({u, 1}); // go against the road: one reversal
}
std::vector<int> dist(n, kInf);
std::deque<int> queue;
dist[from] = 0;
queue.push_back(from);
while (!queue.empty()) {
int node = queue.front();
queue.pop_front();
for (const Arc& arc : g[node]) {
int candidate = dist[node] + arc.cost;
if (candidate < dist[arc.to]) {
dist[arc.to] = candidate;
if (arc.cost == 0) queue.push_front(arc.to);
else queue.push_back(arc.to);
}
}
}
return dist[to] == kInf ? -1 : dist[to];
}
int main() {
std::vector<std::pair<int, int>> roads = {{0, 1}, {2, 1}, {2, 3}, {4, 3}};
std::cout << "reversals from 0 to 4: " << minReversals(5, roads, 0, 4) << '\n';
std::cout << "reversals from 4 to 0: " << minReversals(5, roads, 4, 0) << '\n';
}The output is:
reversals from 0 to 4: 2
reversals from 4 to 0: 2The roads are 0 -> 1, 2 -> 1, 2 -> 3 and 4 -> 3. Starting at 0, you can take 0 -> 1 for free. From 1 you cannot go on, because no road leaves 1. Reversing 2 -> 1 gives 1 -> 2 at cost 1. From 2 you take 2 -> 3 for free. To reach 4, reverse 4 -> 3 at cost 1, which gives 3 -> 4. The total is 2.
This example shows a point that is easy to miss. The algorithm does not know which edges are reversed. It simply sees the reversed arcs as ordinary arcs with cost 1, and the rule for choosing front or back handles everything.
Common mistakes
Mistake 1: pushing every edge to the back. Some people write the same code as above but always call push_back. The answers stay correct. Each node is still relaxed only when it improves, so the result is still a shortest path. The cost is extra work. On 500 random graphs with 0 and 1 costs, the all-back version did about 5% more relaxations than the correct version, and the answers were the same. The gap is small on these graphs. On other graphs it can be bigger, because nodes get re-expanded more often. Push 0-cost edges to the front.
Mistake 2: marking a node as finished the first time it is popped, while pushing 0-cost edges to the back. A common shortcut is a done array. A node is skipped if it is already done. This shortcut is safe only if 0-cost edges go to the front. Here is a four-node graph where it goes wrong. The edges are 0 -> 1 (cost 1), 0 -> 2 (cost 0), 2 -> 1 (cost 0) and 1 -> 3 (cost 1). The program pushes every edge to the back and marks a node done on its first pop. It prints the distances from that version and from Dijkstra's algorithm, which is always right.
visited 0 0 0 2 | dijkstra 0 0 0 1Node 3 gets distance 2 from the visited version and distance 1 from Dijkstra. Node 1 was popped first with stored distance 1 and marked done. Later, node 2 lowered node 1's distance to 0, but node 1 was already done, so its edge to node 3 was never tried again with the lower value. With 0-cost edges pushed to the front, the first pop is final, and the done shortcut gave no wrong answers on 2,000 random graphs. Use the shortcut only with the front rule.
Mistake 3: swapping the rule. Some people push cost 1 edges to the front and cost 0 edges to the back. On 2,000 random graphs the answers still matched Dijkstra's, so the mistake does not show up as a wrong number in a quick test. It shows up as extra work. The most times any node was pushed rose from 2 to 5 on 2,000 random graphs. The order that the proof relies on is gone, and so is the two-push bound. Keep the rule: 0 to the front, 1 to the back.
Mistake 4: using a vector instead of a deque. The method needs push_front. A std::vector does not have it, and the compiler says so. This is the exact error message from g++ 15.2.0 when the file contains std::vector<int> queue; queue.push_front(3);:
err1.cpp: In function ‘int main()’:
err1.cpp:4:11: error: ‘class std::vector<int>’ has no member named ‘push_front’
4 | queue.push_front(3);
| ^~~~~~~~~~Change the declaration to std::deque<int>, and add #include <deque>.
Mistake 5: a sign comparison warning. A common loop over the distances looks like this:
for (int i = 0; i < dist.size(); ++i) total += dist[i];With -Wall, g++ 15.2.0 prints a warning. The code still runs, but the warning is worth fixing, because size() returns an unsigned number and i is signed.
warn1.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
6 | for (int i = 0; i < dist.size(); ++i) total += dist[i];
| ~~^~~~~~~~~~~Write for (std::size_t i = 0; i < dist.size(); ++i) or use a range-based for loop.
Mistake 6: using negative costs. The proof depends on costs being 0 or 1. With a cost of -1, a candidate can fall below the level being processed, so the two-push bound and the sorted order no longer hold. A cycle whose total cost is negative makes it worse. Take a two-node loop, 0 -> 1 with cost 0 and 1 -> 0 with cost -1. Each trip around the loop lowers the distance by 1, so the method never stops. The program stopped only when I capped it at 200,000 pops. Check that all costs are 0 or 1 before you use this method. For other costs, use Dijkstra when all costs are non-negative, and Bellman-Ford when some are negative.
Mistake 7: forgetting that the answer can be unreachable. dist[target] stays at kInf when no path exists. Printing that number gives a huge value such as 2147483647. Check for kInf and report -1 or whatever your problem asks for.
Practice
Exercise 1. A graph has four nodes and these edges: 0 -> 1 (cost 1), 0 -> 2 (cost 1), 1 -> 2 (cost 0), 2 -> 3 (cost 1), 1 -> 3 (cost 1). Starting at node 0, what is the distance to node 3? Work it out on paper, then check with the function.
Show the answer
The distance is 2. Node 1 is reached at cost 1. Node 2 is reached at cost 1 directly, and also at cost 1 through node 1 with a free edge. Node 3 is reached from node 2 at cost 1 + 1 = 2, or from node 1 at cost 1 + 1 = 2. The full distance list is 0 1 1 2.
Exercise 2. Explain in your own words why a cost 0 edge goes to the front of the deque and not the back. Use a small example with two nodes.
Show the answer
Suppose node u has distance 3 and is at the front of the deque. A free edge from u to v gives v distance 3 as well. Node v is just as close as the node we just served, so it should be served next. If we put v at the back, all the other nodes at distance 3 or 4 would be served first, and v would be handled late. Late handling wastes work, and the proof needs the deque sorted, which only the front rule keeps.
Exercise 3. Use minWallsBroken on the grid "...", "###", "..." with a row of walls in the middle. What does it return, and why?
Show the answer
It returns 1. The walls fill the whole middle row, so you must go through one of them. Breaking one wall costs 1, and after that every other square is open, so the total is 1.
Exercise 4. The roads are 0 -> 1, 1 -> 2 and 3 -> 2. What is the fewest reversals needed to go from node 0 to node 3? Check your answer with minReversals.
Show the answer
It is 1. Go 0 -> 1 -> 2 for free. From node 2, reverse the road 3 -> 2 to get 2 -> 3 at cost 1. The total is 1.
Exercise 5. A node can be in the deque at most twice. Suppose you add a counter that records how many times each node is pushed, and you run it on a graph with 1,000 nodes. What is the largest value the counter can show for any node, and why?
Show the answer
The largest value is 2 for a node that was reached by a cost 1 edge first and later improved by a cost 0 edge. The first push has value d + 1, and any later improvement can only give d, because nothing in the deque is smaller than d. A node cannot improve past d, so there is no third push. The start node is pushed once, so its count is 1.
Summary
- 0-1 BFS finds the cheapest distances when every edge costs 0 or 1, in time proportional to nodes plus edges.
- A deque is the container: cost 0 edges go to the front, cost 1 edges go to the back.
- The deque stays sorted by distance, which is why the first pop of a node is final.
- Each node is pushed at most twice, so the method does little extra work.
- Negative costs break the guarantees, and an unreachable target shows up as infinity, so check for it.
- A
donearray is safe only when 0-cost edges go to the front.