Skip to main content
Module 6 · Dijkstra's Algorithm (optional)

Lesson 6-3 · From BFS to Dijkstra — Knowledge ChecksAnswer key

Correct answers are marked and the explanation follows each question.

  1. Why can BFS get away with taking the oldest intersection off to_visit, and Dijkstra cannot?

    1. A.BFS lists are shorter
    2. 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✓
    3. C.Dijkstra uses a dictionary and BFS uses a list
    4. D.It can; the change is only for speed

    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.

  2. In Dijkstra, what happens when the planner reaches an intersection it has already recorded, by a cheaper route?

    1. A.Nothing — the first way found is kept, as in BFS
    2. B.distance and previous for that intersection are overwritten with the cheaper total and the new way in✓
    3. C.The planner stops and returns the path
    4. D.The intersection is added to BLOCKED

    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.

  3. On a grid with no blocked intersections and no slow edges, how do the three planners' paths compare?

    1. A.Dijkstra's paths are shorter
    2. B.All three are the same length; the planners only disagree when a wall or a slow segment gives them a reason to✓
    3. C.Manhattan fails
    4. D.BFS and Dijkstra return []

    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.

  4. In the cost grid above, why is (0, 2) a 4 rather than a 2?

    1. A.A typo in the grid
    2. 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✓
    3. C.Because (0, 2) is blocked
    4. D.Because the grid is 4 wide

    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.