Overview
0-1 BFS uses a deque instead of a heap: relaxing a zero-cost edge pushes the neighbor to the front, while relaxing a one-cost edge pushes it to the back.
CoreSource checked
0-1 BFS
Finds shortest paths in graphs whose edge weights are only 0 or 1.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Shortest Path
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Zero-one BFS
Core Concepts
shortest paths with binary weightsshortest pathpathfinding
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)
When to Use
- Use when every edge weight is exactly 0 or 1.
- Use when Dijkstra's algorithm would work but a deque is simpler and faster.
When Not to Use
- Avoid when any edge has weight outside {0, 1}.
- Avoid when negative weights or heuristic search are required.
What It Does
- Maintains shortest known distances
- Processes zero-cost edges before one-cost edges
- Uses a deque to avoid heap overhead
Use Cases
- Shortest paths with binary edge costs
- Grid problems with free and costly moves
- State graphs where transitions have cost 0 or 1
Inputs
- Shortest Path input instance for shortest path
- Configuration parameters controlling shortest paths with binary weights
Outputs
- Computed shortest path solution produced by 0-1 BFS
- Diagnostic state over shortest paths with binary weights and shortest path
Pseudocode
- 1.Set all distances to infinity and start distance to 0
- 2.Push the start node into a deque
- 3.Pop a node from the front
- 4.For each outgoing edge, relax the neighbor distance
- 5.Push the neighbor front for weight 0 or back for weight 1
- 6.Return distances and predecessors
Canonical Example
- Input
- edges A->B cost 0, B->C cost 1, A->C cost 1
- Output
- dist[B] = 0 and dist[C] = 1
- Explanation
- The zero-cost edge to B is processed from the front of the deque before one-cost alternatives.
Implementation Notes
- Relax edges just like Dijkstra, but use push-front for weight 0 and push-back for weight 1.
- Store distances and only process an update when it improves the distance.
- Test with zero-cost cycles and multiple equal shortest paths.
Common Pitfalls
- Pushing all relaxed nodes to the same deque end loses the ordering invariant.
- Marking nodes visited too early can miss a later zero-cost improvement.
- Using it on weights larger than 1 gives incorrect distances.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow using a deque to process zero-cost edges before one-cost edges on a small shortest paths with binary weights example.
S
#
#
#
#
#
#
#
G
Step 1 of 6: Set all distances to infinity and start distance to 0
pathfinding-mechanismNotes
0-1 BFS is a specialized shortest-path algorithm, not a general replacement for Dijkstra.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for 0-1 BFS invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Conceptual neighborVisibility Graph Roadmap
Pathfinding · Core
0-1 BFS and Visibility Graph Roadmap both relate to shortest paths with binary weights, but use different structures or assumptions.
Compare with thisRelationships
View full relationship pageConceptual neighborVisibility Graph Roadmap
0-1 BFS and Visibility Graph Roadmap both relate to shortest paths with binary weights, but use different structures or assumptions.
Conceptual neighborDial's Algorithm
0-1 BFS and Dial's Algorithm both relate to shortest paths with binary weights, but use different structures or assumptions.
Conceptual neighborEppstein K Shortest Paths
0-1 BFS and Eppstein K Shortest Paths both relate to shortest paths with binary weights, but use different structures or assumptions.
Related Algorithms
Tags
PathfindingGraph