Zero–One BFS Deque
Put free moves at the front and unit-cost moves at the back.
Free theory articlePut free moves at the front and unit-cost moves at the back.
Concept & interpretation
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.
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.