0-1 BFS
A deque replaces the heap when weights are 0 or 1: a 0 edge pushes to the front, a 1 edge to the back.
Shortest Paths: 0-1 BFS with a deque
Edge 0 to 1 weighs 1: 0 + 1 = 1 against 1's current infinity. Shorter, so 1 becomes 1 and joins the back of the deque: one step further than 0. Deque now 1.
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Space
- O(V)
Before this
Related
Taught by the same lesson
Shortest Paths covers these too, in the same run.