0-1 BFS (Deque Optimization)
Software Engineer path · lesson 31 of 99Shortest 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.
Undirected; every weight must be 0 or 1.
Source A. 0-weight edges go to the front of the deque, 1-weight edges to the back.
- 1dist[src] = 0; deque = [src]
- 2while deque:
- 3 u = deque.popleft()
- 4 for (v, w) in edges(u): # w is 0 or 1
- 5 if dist[u] + w < dist[v]:
- 6 dist[v] = dist[u] + w; w == 0 ? push v to FRONT : push v to BACK
- Pops
- 0 / 5
- Front pushes
- 0 / 2
- Back pushes
- 0 / 2
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
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
References & Further Reading
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