Shortest Paths

How maps find routes

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

What you’ll learn

• Weighted graphs model roads, networks and costs.
• Dijkstra’s algorithm finds shortest paths by settling the closest point first.
• Greedy choices can fail. Keep track of total distances.

Steps

1. Find the route
2. Dijkstra’s algorithm
3. Fewest roads
4. A wave through the maze
5. Traffic jam
6. Counting shortest routes
7. Greedy fails