AlgoScope

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 path, algorithm, advanced
Edge 0 to 1: 1 against infinity. Pushed.101011000112345u
Edge 0 to 1: 1 against infinity. Pushed.101011000112345u

Shortest Paths: 0-1 BFS with a deque

Decision, step 3 of 22

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.

How shortest paths works

Cost

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Taught by the same lesson

Shortest Paths covers these too, in the same run.