Artificial Intelligence / AI 0083 · Atom · ~20 seconds
The Fewest-Steps Guarantee
Video not yet published
to the StudyWalks catalog
to the StudyWalks catalog
State
Breadth-first search is guaranteed to find a solution with the fewest steps, because the queue serves paths strictly in length order.
Show
On Riverbend it returns a three-road route to Grandmother's, and no shorter route exists.
Watch for
The guarantee is structural, not lucky — every shorter candidate is tried and exhausted first.