A special weighted case
When every edge weight is either zero or one, you can find shortest paths faster than Dijkstra by using a double ended queue, or deque, instead of a priority queue. This trick is common in grid problems where some moves are free and others cost one.
Front or back
The deque keeps vertices roughly sorted by distance using a clever rule during relaxation.
- A zero weight edge does not increase distance, so push the neighbor to the front of the deque.
- A one weight edge increases distance by one, so push the neighbor to the back.
Always pull from the front. Front pushes keep equal distance vertices grouped, and back pushes place the next distance layer behind them. This preserves the property that the deque is ordered by distance without the logarithmic cost of a heap.
Why it is faster
A heap based Dijkstra pays a logarithmic factor for ordering. Zero one BFS exploits the limited weight set so each vertex is processed in nearly constant amortized time, giving a running time proportional to the graph size.
Key idea
With only zero and one edge weights, a deque that pushes zero edges to the front and one edges to the back finds shortest paths without a heap.