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.
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.
What you will see
The deque beside the graph; zero-weight neighbours jump the line.
Cost
| Best | O(V + E) |
|---|---|
| Average | O(V + E) |
| Worst | O(V + E) |
| Space | O(V) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Vertices announce name, tentative distance and parent; each step announces the relaxation and whether it improved a distance.
Reduced motion: Distance updates change the label with a crossfade instead of radiating from the edge.
Before this
Related
Taught by the same lesson
Shortest Paths covers these too, in the same run.