0-1 BFS (Deque Optimization)
Shortest path when edge weights are only 0 or 1. Uses deque instead of priority queue for O(V+E) instead of O(E log V). Critical for grid problems with obstacles.
0-1 BFS (Deque Optimization)
Shortest path when edge weights are only 0 or 1. Uses deque instead of priority queue for O(V+E) instead of O(E log V). Critical for grid problems with obstacles.
0-1 BFS: find shortest path from node 0. Start: dist[0]=0. Use deque (double-ended queue): weight-0 edges go to FRONT, weight-1 to BACK.
Front or back of the deque?
Sort each case by where 0-1 BFS puts (or takes) the node.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
Front
Drop items hereBack
Drop items hereTest your knowledge
Why is 0-1 BFS faster than Dijkstra for 0-1 weight graphs?
The short version
Imagine walking through a city where some roads are free (weight 0) and others cost a toll (weight 1). With 0-1 BFS, free roads get priority in line, so you always take the cheapest path first.
In more depth
When Dijkstra is Overkill
If edge weights are only 0 or 1, we don't need a full priority queue. A deque suffices!
Algorithm:
Why It Works:
Deque maintains sorted order by distance because:
Key Gotchas:
When to reach for this
- Graph with edge weights 0 and 1 only
- Grid where some moves are free and others cost 1
- Obstacle removal on a grid
- Keywords: 'minimum cost', 'binary weight edges'
Interview Questions
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required