Where it runs
1. The problem
In the last lesson Dijkstra's algorithm found the cheapest route across a weighted map. Each time, it took from a min-heap the cheapest node whose price was not final yet. The heap is what puts the log factor into its running time. When weights can be any number, you need the heap.
But in many real graphs an edge has only two possible prices: 0 or 1. The example from this lesson's real case is a datacenter where servers stand in racks. A hop between servers of the same rack counts as free (0), and a hop to another rack costs 1. You want to know how many rack-to-rack hops it takes to reach each server.
When the weights are only 0 and 1, you can drop the heap. A double-ended queue does the same job faster, in O(V + E). This trick is called 0-1 BFS.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Shortest path problems where each move costs 0 or 1, such as walls you may break or arrows you may change. A deque replaces the heap, with free moves pushed to the front and paid ones to the back, in O(V + E).
Stepping onto an empty cell costs 0 and onto an obstacle costs 1, so it is the lesson's zeroOneShortest on a grid.
Following a cell's arrow costs 0 and any other direction costs 1.
The state is lane and position, moving forward costs 0 and a side jump costs 1.