cf.completefrontend
GRAPHS · ADVANCED

0-1 BFS

Find cheapest paths when every edge costs either 0 or 1, using a double-ended queue instead of a heap.

Time O(n + e)Space O(n + e)3 practice problemsStep-through picture

The idea

Plain BFS assumes every edge costs 1. Dijkstra's algorithm handles any non-negative cost but needs a priority queue. There is a common middle case: every edge costs either 0 (free) or 1. Examples are "walking is free, breaking a wall costs 1" or "following a link the right way is free, going against it costs 1".

0-1 BFS handles this with a deque, a list you can add to at both ends. When you find a cheaper way to a node using a free edge, you put that node at the front, because it is just as close as the current node. When you use a cost-1 edge, you put it at the back, like normal BFS.

This keeps the deque sorted by distance at all times, so nodes come out cheapest first, just as in Dijkstra's algorithm, but without a heap.

An everyday example

Moving walkways in an airport

In an airport, some corridors have moving walkways that carry you for free, and others you must walk, which costs you one unit of effort. When a free walkway opens up from where you stand, you take it right away, because it doesn't cost anything. Corridors that cost effort go on your to-do list for later.

How the example maps to the code
In the exampleIn the code
A free moving walkwayAn edge with weight === 0
A corridor you must walkAn edge with weight === 1
Taking the free walkway right awaydeque.unshift(next)
Adding a walk to the end of the to-do listdeque.push(next)
The least effort to reach a gatedist[next]

From the slow way to 0-1 bfs

  1. When edges cost 0 or 1, plain BFS gives wrong answers, because it counts a free edge as a full step. The safe choice is Dijkstra's algorithm with a heap, which costs O(e log n). That works, but it is more machinery than this problem needs.
  2. Watch what Dijkstra's heap holds when every cost is 0 or 1. The node taken out has the smallest distance, d. Its edges only create distances d or d + 1. So the heap only ever holds two different distance values at once: d and d + 1. A full heap is only being used to sort two values.
  3. A deque, a list you can add to at both ends, can keep that two-value order by itself. A free edge gives a node the same distance d as the current node, so it goes to the front with the other d nodes. A cost-1 edge gives d + 1, so it goes to the back.
  4. One more change from plain BFS: a node's first distance is not always its final one, because a free path to it may turn up later. So instead of a visited mark, compare with dist and update whenever a cheaper cost appears, even if that puts a second copy of the node in the deque. That loop is 0-1 BFS.

How it works

  1. Build graph with [to, weight] pairs, where each weight is 0 or 1.
  2. Set every dist to Infinity, then dist[start] = 0, and put start in the deque.
  3. Take node from the front of the deque.
  4. For each edge [next, weight], skip it if dist[node] + weight is not smaller than dist[next].
  5. Otherwise update dist[next]. If weight is 0, add next to the front; if it is 1, add it to the back.
  6. When the deque is empty, dist holds the cheapest cost to every node.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function zeroOneBfs(n, edges, start) {
  2. const graph = Array.from({ length: n }, () => []);
  3. for (const [from, to, weight] of edges) graph[from].push([to, weight]);
  4. const dist = new Array(n).fill(Infinity);
  5. dist[start] = 0;
  6. const deque = [start];
  7. while (deque.length > 0) {
  8. const node = deque.shift();
  9. for (const [next, weight] of graph[node]) {
  10. if (dist[node] + weight >= dist[next]) continue;
  11. dist[next] = dist[node] + weight;
  12. if (weight === 0) deque.unshift(next);
  13. else deque.push(next);
  14. }
  15. }
  16. return dist;
  17. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

With a real deque each push and pop takes constant time, and with costs of only 0 and 1 each node is improved only a few times. The adjacency list holds every edge.

  • Best caseO(n + e)

    Building graph reads every edge, even when start has no outgoing edges and the loop runs only once.

  • Average caseO(n + e)

    Each node enters the deque at most twice, and each entry reads that node's edges once.

  • Worst caseO(n + e)

    Every node is improved once, so it enters twice and its edges are read twice. That is with a real deque; the template's shift and unshift move the whole array and can be much slower on big inputs.

Common mistakes

  • Using plain BFS and counting every edge as a step, which ignores the free edges.
  • Adding free-edge nodes to the back. The deque is no longer sorted and some distances come out too big.
  • Marking nodes as done the first time they are seen, as in plain BFS. A later free edge can still make them cheaper, so compare with dist instead.
  • Using it with costs like 2 or 5. It only works for 0 and 1; use Dijkstra's algorithm otherwise.

When to use it

Look for these clues in a problem:

  • Every move costs either 0 or 1, never anything else.
  • The question asks for the fewest walls to break, cells to change, or edges to reverse.
  • Some moves are free and others count, as in "following an arrow is free, changing it costs 1".
  • Plain BFS gives wrong answers because not every edge counts as a step.

Check yourself

Answer each one in your head first, then open it.

Why can't 0-1 BFS mark a node as done the first time it gets a cost, like plain BFS does?

A cheaper free route can show up later. In the trace, 4 first got cost 2 and was later improved to 1 through 2 → 3 → 4.

At most how many times can one node enter the deque?

Twice. Its first cost is d or d + 1, and later costs can't go below d, so it can improve at most once.

In the trace, what did the old copy of 4 change?

Nothing. It re-checked 4 → 5, found 1 + 1 was not less than dist[5] = 2, and was done.

Why does the deque never hold more than two different labels?

Entries are only added with the current smallest label d or with d + 1, and the smallest label never goes down. So everything in it is d or d + 1.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Give each deque entry a label: the distance its node had when the entry was added. The rule is that labels read from front to back never go down, and they hold at most two values, d and d + 1. At the start the deque holds only the start, labeled 0.

Taking the front entry removes a smallest label, d. A free edge adds a label d at the front, which is still the smallest. A cost-1 edge adds d + 1 at the back, which is at most the largest. So the rule holds, and entries come out in order of label, just as Dijkstra's heap hands out its smallest item. Dijkstra's argument then applies: when an entry comes out with a label equal to dist[node], that cost is final, because every later entry has a label at least as large and edges never cost less than 0.

It ends because costs only go down. When a node first gets a cost, it is d or d + 1, and later entries all have labels of at least d, so a node can improve at most once, from d + 1 to d. Each node therefore enters the deque at most twice. An old copy, like the second 4 in the trace, comes out after the newer copy already tried every edge with the lower cost, so it never pushes anything.

Going deeper

3 more ideas

Why the deque stays sorted

At any moment the deque holds nodes with at most two distances: some with distance d and some with d + 1, with the d ones in front. A free edge from a d node gives another d node, which goes to the front. A cost-1 edge gives a d + 1 node, which goes to the back. Neither breaks the order, so the front is always a cheapest node, the same promise a heap gives Dijkstra.

Cost compared with Dijkstra

Each improvement adds a node to the deque in O(1), and with costs of only 0 and 1 a node can only be improved a few times. The whole run is O(n + e) with a real deque, compared with O((n + e) log n) for Dijkstra with a heap.

About shift and unshift

JavaScript arrays have shift and unshift, but they move every element, so they are slow on big inputs. For large graphs, build a deque from a fixed-size array with head and tail indexes that wrap around, or keep two arrays: a "current distance" list and a "next distance" list.

Work it by hand

Every step in a table, with why

Cheapest costs from node 0 in a directed graph where the route through 2 and 3 uses free edges.

n = 6, edges = [[0, 1, 1], [0, 2, 1], [1, 4, 1], [2, 3, 0], [3, 4, 0], [4, 5, 1], [3, 5, 1]], start = 0

StepnodeEdges trieddistdeque afterWhat happensWhy
1--[0, ∞, ∞, ∞, ∞, ∞][0]StartOnly the start has a cost. ∞ stands for Infinity, no path found yet.
200→1 (1), 0→2 (1)[0, 1, 1, ∞, ∞, ∞][1, 2]Both go to the backBoth edges cost 1, so 1 and 2 get cost 1 and join the back.
311→4 (1)[0, 1, 1, ∞, 2, ∞][2, 4]dist[4] = 2The first route to 4 costs 2. It isn't final: a cheaper route will show up.
422→3 (0)[0, 1, 1, 1, 2, ∞][3, 4]Free edge: front3 costs the same as 2, so it goes to the front, ahead of 4.
533→4 (0), 3→5 (1)[0, 1, 1, 1, 1, 2][4, 4, 5]dist[4] drops to 11 + 0 = 1 beats 2, so dist[4] improves and a second copy of 4 goes to the front. 5 gets cost 2 at the back.
644→5 (1)same[4, 5]No change1 + 1 = 2 is not less than dist[5] = 2, so the edge is skipped.
744→5 (1)same[5]The old copyThis is the copy pushed when dist[4] was 2. It reads the same edge again and changes nothing.
85none[0, 1, 1, 1, 1, 2][]Stop5 has no outgoing edges, and the deque is empty.

It returns [0, 1, 1, 1, 1, 2]. Plain BFS would count edges instead and say 4 is 2 steps and 5 is 3 steps away, but the free edges make them cost 1 and 2.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
0-1 BFSO(n + e)O(n + e)Every edge costs exactly 0 or 1.
Breadth-first searchO(n + e)O(n)Every edge costs the same, so only the number of edges matters.
Dijkstra's algorithmO(e log n)O(n + e)Costs are any non-negative numbers, such as travel times.
Bellman-FordO(n · e)O(n)Some costs are negative, or you must detect a negative loop.

Extra memory: O(n + e): the adjacency list holds every edge, dist holds n numbers, and the deque holds at most 2n entries.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for 0-1 BFS and the other approaches, on a scale where each line up is 10 times more steps.
  • 0-1 BFS, Breadth-first search O(n + e)
  • Dijkstra's algorithm O(e log n)
  • Bellman-Ford O(n · e)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
0-1 BFS202,0002 million
Breadth-first search202,0002 million
Dijkstra's algorithm339,96620 million
Bellman-Ford1001 million1 trillion

Inputs that need care

5 tricky inputs
A node that can't be reached
It is never pushed and keeps Infinity. Convert it at the end if the problem wants -1.
Every edge costs 1
Every push goes to the back, so it behaves exactly like plain BFS, and each node enters once.
Every edge costs 0
Every push goes to the front, and every reachable node ends with cost 0. The order looks like a depth-first walk.
Two edges between the same nodes, one costing 0 and one costing 1
Both are tried. The free one gives the lower cost, and the >= check makes the other one change nothing.
An edge that costs 2 slips into the input
It would go to the back with label d + 2, which breaks the two-value rule, and nodes can come out before their cost is final. Use Dijkstra's algorithm for costs other than 0 and 1.

Variations and follow-ups

Twists interviewers add

Fewest walls to break on a grid

Moving into an open cell costs 0 and moving into a wall costs 1. Run 0-1 BFS over cells with the four directions, and dist of the target cell is the fewest walls broken.

Fewest edges to reverse

For each directed edge a → b, add a → b with cost 0 and b → a with cost 1. The cheapest cost from the start to the target is the fewest edges you must flip to make a path.

Skipping old copies

Push [node, cost] pairs instead of plain nodes. When a pair comes out with a cost bigger than dist[node], skip it, the same trick Dijkstra's algorithm uses.

Small whole-number costs

If costs are whole numbers from 0 to k, keep k + 1 buckets in a circle instead of a deque. This is called Dial's algorithm, and it avoids a heap as long as k is small.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "fewest walls to break", "fewest arrows to change", or "fewest edges to reverse": some moves are free and the others each cost one.
  • Explain the deque in one sentence: "free edges go to the front because they keep the same cost; cost-1 edges go to the back, so the deque stays sorted like Dijkstra's heap".
  • Test by hand on a graph where a free route improves a node that already has a cost, as with node 4 in the trace. That is the case where code with a plain visited mark fails.
  • Expect "what if costs go up to 5?". Answer: the two-value rule breaks, so use Dijkstra's algorithm, or Dial's buckets for small whole numbers.

Where frontend code uses it

The same idea in real UI code
  • Grid map tools where walking on open ground is free and crossing an obstacle costs one action, such as "fewest walls to remove".
  • Navigation over a link graph where following a link forward is free but using the browser's back button counts as one extra action.
  • Puzzle games in the browser that count only some kinds of moves, such as "rotations used", while other moves are free.

Related algorithms