Lesson 6-3 · From BFS to Dijkstra — Knowledge ChecksAnswer key
Why can BFS get away with taking the oldest intersection off to_visit, and Dijkstra cannot?
In BFS, the wave front is the same number of steps and the same cost from the start at once. Weights break that: cost no longer grows in step with order of discovery, so the planner has to look up which waiting intersection is cheapest.
In Dijkstra, what happens when the planner reaches an intersection it has already recorded, by a cheaper route?
That is change 2. BFS never reconsiders because its first discovery is already shortest in steps. Dijkstra may find a cheaper way later and must keep it, including the previous pointer that the walk-back will follow.
On a grid with no blocked intersections and no slow edges, how do the three planners' paths compare?
Without obstacles, every planner finds a shortest Manhattan route. Walls separate Manhattan from the other two; weights separate BFS from Dijkstra. Each upgrade earns its keep on exactly the grid that needs it.
In the cost grid above, why is (0, 2) a 4 rather than a 2?
Every other cell matches the BFS distance numbers. (0, 2) is the one place the slow segment is on the direct route, and the printed 4 is the cheaper way round it.