Sign in to watch this lesson
Algorithms - Graphs II · 4:17
0-1 BFS and Dial's Algorithm
When every edge costs 0 or 1, Dijkstra's heap only ever holds two distinct labels, so two plain vectors replace it and shortest paths take linear time. We solve an arrow-grid puzzle with two conveyor belts, see why marking cells visited on push gives wrong answers, compare the deque form, and extend the idea to weights 0..k with Dial's ring of k + 1 buckets, measured against a heap.
You will learn
- Explain why Dijkstra's queue holds only labels d and d + 1 when all weights are 0 or 1
- Implement 0-1 BFS with two vectors (or a deque) in O(V + E) and run it by hand on a grid
- Avoid the visited-on-push bug by comparing labels, and explain why stale copies and stack order are harmless
- Implement Dial's algorithm with k + 1 cyclic buckets for integer weights in 0..k