How Your GPS Finds the Shortest Route in Seconds
Navigation runs a layer-by-layer greedy search from the start point, so every intersection is only locked in once with its shortest arrival — and the answer falls out the instant the destination is reached.
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 7 scenes and explore, respond, and learn as you go.
How can a navigation app compute the shortest route across a whole city in just a few seconds?
Your phone plots a route across millions of intersections in just a few seconds.
Brute-force checking every possible path would take more than a lifetime, so how can the answer arrive so fast?
A ripple-style animation showing routes expanding outward from a start point, with each intersection locked in the moment it is reached.
Navigation uses a wave-like greedy search: starting from your location, it expands outward layer by layer, and each intersection is only confirmed the first time the shortest arrival is recorded.
To guarantee the shortest path, the app must try every possible route and compare them.
- weighted graph theory
- code implementation
- A* heuristics
- real-time traffic re-routing
- 01A Shortest Route in Just Seconds?slide
- 02What Do You Think?quiz
- 03Why Trying Every Path Is Impossibleslide
- 04Expanding Outward in Wavesslide
- 05Where This Trick Stops Workingslide
- 06Try It: Food Delivery Dispatchinteractive
- 07The Answerslide
Discussion threads for a Stage aren't available yet.
