Why can BFS get away with taking the oldest intersection off to_visit, and Dijkstra cannot?
- A.BFS lists are shorter
- B.When every step costs 1, the oldest entry is always among the closest; with weights, something that went on later by a cheap route can be closer than something that went on earlier by a slow one
- C.Dijkstra uses a dictionary and BFS uses a list
- D.It can; the change is only for speed
Answer Why?
In Dijkstra, what happens when the planner reaches an intersection it has already recorded, by a cheaper route?
- A.Nothing — the first way found is kept, as in BFS
- B.distance and previous for that intersection are overwritten with the cheaper total and the new way in
- C.The planner stops and returns the path
- D.The intersection is added to BLOCKED
Answer Why?
On a grid with no blocked intersections and no slow edges, how do the three planners' paths compare?
- A.Dijkstra's paths are shorter
- B.All three are the same length; the planners only disagree when a wall or a slow segment gives them a reason to
- C.Manhattan fails
- D.BFS and Dijkstra return []
Answer Why?
In the cost grid above, why is (0, 2) a 4 rather than a 2?
- A.A typo in the grid
- B.Reaching it straight up the left edge costs 1 + 5 = 6 because of the slow segment; the detour through x = 1 costs 4, and Dijkstra keeps the cheaper total
- C.Because (0, 2) is blocked
- D.Because the grid is 4 wide
Answer Why?