0-1 BFS with a Deque
Shortest paths when weights are 0 or 1.
A Special Kind of Graph
Some graphs only have edge weights of 0 or 1. There you can beat Dijkstra with a simpler, faster trick.
Meet 0-1 BFS
0-1 BFS finds shortest paths on 0/1-weighted graphs in linear time, with no heap and no log factor at all.
All lessons in this course
- Dijkstra with a Heap
- 0-1 BFS with a Deque
- Bellman-Ford & Negative Edges
- Floyd-Warshall All-Pairs