Shortest Paths

How sat-navs find the best route

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Maps become weighted graphs; routes are paths.
• Dijkstra settles the closest unsettled node and relaxes its neighbours.
• It needs non-negative edge lengths.

Steps

1. Roads as a graph
2. Dijkstra’s algorithm
3. Pick the route
4. Negative roads?
5. Roads between every town
6. Every pair