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

Lesson 6-3 · From BFS to Dijkstra — Knowledge Checks

Name Date
  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

    Answer Why?

  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

    Answer Why?

  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 []

    Answer Why?

  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

    Answer Why?