Lesson 5-2 · Finding the Path — Knowledge ChecksAnswer key
Walking downhill, you are on an intersection numbered 4. Its open neighbors are numbered 3, 3 and 5. Where can you step?
Any neighbor with one less works. Two choices just means two different shortest paths, both correct.
Why does the computer take intersections from the FRONT of the to-visit list?
New intersections go on the end, so the front is always the oldest. Oldest-first means the wave front moves out one step at a time, which is what makes every number a shortest distance.
What in the algorithm makes sure no intersection is ever numbered twice?
A neighbor that already has a number is left alone. That is the numbered-once rule from Lesson 5-1.
What makes sure everything 1 step from the destination is numbered before anything 2 steps away?
Joining at the end and taking from the front means the oldest is always next, so the wave front moves out one step at a time.