Lesson 3 · Dijkstra's Algorithm — The Concept — Knowledge ChecksAnswer key

What does the previous dictionary store?

1. A.The distance from the start to each node
2. B.Which node you came from to reach each node — used to rebuild the path✓
3. C.The list of blocked nodes
4. D.How many neighbors each node has

previous records each node's predecessor on the shortest path. Tracing it backward from the destination reconstructs the route.

Which unvisited node does Dijkstra visit next?

1. A.The one closest to the destination
2. B.The one with the smallest known distance from the start✓
3. C.The most recently updated one
4. D.A random one

Dijkstra has no notion of 'distance to the destination.' It always expands the nearest unvisited node measured from the start.

At step 7, visiting (2,1) offers (2,2) a distance of 3+1=4, but (2,2) already has distance 4. What happens?

1. A.(2,2) is updated to 4 again
2. B.No change — the new distance is not smaller than the existing one✓
3. C.The algorithm crashes
4. D.(2,2) is marked visited early

Dijkstra only updates when the new path is strictly shorter. 4 is not less than 4, so (2,2) keeps its existing distance and previous.

Why must the reconstructed path be reversed?

1. A.To make it look nicer
2. B.Because tracing previous goes from destination back to start — reversing puts it in start-to-destination order✓
3. C.Dijkstra always returns paths backward by mistake
4. D.It doesn't need to be reversed

You follow previous backward (destination → start), so the collected list is reversed. Flipping it gives the forward path the robot drives.

On a clear grid with no obstacles, how does Dijkstra's path length compare to Manhattan's?

1. A.Always shorter
2. B.The same length (the exact route may differ)✓
3. C.Always longer
4. D.Unpredictable

With no obstacles, both find an optimal path of equal step count. Dijkstra's real advantage shows up only when obstacles are present.