Zero–One BFS Deque
Put free moves at the front and unit-cost moves at the back.
By Riano · Published · Updated · Report a correction
Zero–One BFS Deque
The 0-1 Breadth-First Search (BFS) algorithm is used for finding shortest paths in a directed graph where every edge has a weight of exactly 0 or 1. By utilizing a double-ended queue (deque), it processes zero-weight edges by pushing the target vertex to the front of the deque and one-weight edges by pushing to the back. This ensures that vertices are always relaxed and expanded in monotonically increasing order of their shortest-path distance from the source.
Worked Example
Consider the Shortcut graph configuration, finding the shortest path from vertex 0 to vertex 4. The edges are: (0,1,1), (0,2,0), (2,1,0), (1,3,1), (2,3,1), (3,4,0).
Initialization: Distances: [0, ∞, ∞, ∞, ∞] Deque: [0] Step 1 (Pop 0): - Edge (0,1,1): Distance to 1 becomes 0 + 1 = 1. Push 1 to back. - Edge (0,2,0): Distance to 2 becomes 0 + 0 = 0. Push 2 to front. Distances: [0, 1, 0, ∞, ∞] Deque: [2, 1] Step 2 (Pop 2): - Edge (2,1,0): Distance to 1 becomes min(1, 0 + 0) = 0. Push 1 to front. - Edge (2,3,1): Distance to 3 becomes 0 + 1 = 1. Push 3 to back. Distances: [0, 0, 0, 1, ∞] Deque: [1, 1, 3] Step 3 (Pop 1 from front, distance 0): - Edge (1,3,1): Distance to 3 becomes min(1, 0 + 1) = 1. (No strict improvement, so not pushed). Distances: [0, 0, 0, 1, ∞] Deque: [1, 3] Step 4 (Pop 1 from front, distance 1, stale entry - skipped): Deque: [3] Step 5 (Pop 3 from front, distance 1): - Edge (3,4,0): Distance to 4 becomes 1 + 0 = 1. Push 4 to front. Distances: [0, 0, 0, 1, 1] Deque: [4] Step 6 (Pop 4, no outgoing edges): Distances: [0, 0, 0, 1, 1] Deque: [] Final Distances: 0, 0, 0, 1, 1 Target 4 Distance: 1
Experiment
You can interact with the Zero–One BFS Deque module to trace through graph traversals manually.
- Set the Graph to
Shortcut. - Set the Source to
0and Target to4. - Click the Step button repeatedly to observe how the deque updates. Notice that traversing zero-weight edges places vertices at the front of the queue, ensuring they are visited next.
- Observe the stale popped entry logic when a vertex is reached via a shorter path after being enqueued but before being processed.
- Change the Graph to
Zero cycleand trace through the steps. The strict improvement check prevents infinite loops in zero-weight cycles.
Limitations
The 0-1 BFS algorithm strictly requires edge weights to be exactly 0 or 1. It does not generalize to arbitrary positive weights, where Dijkstra's algorithm would be necessary, nor can it handle negative weights, which require Bellman-Ford. Additionally, this implementation handles multiple pushes of the same vertex (if a shorter path is found) but relies on skipping "stale" popped entries by comparing the popped distance to the current known shortest distance, ensuring efficiency.
References
The properties and correctness of the 0-1 BFS algorithm are discussed in competitive programming literature, demonstrating how to optimize standard shortest path finding on constrained graphs.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Zero–One BFS Deque module.
Try Zero–One BFS Deque on Riano →