The shortest road between towns
Find the shortest way by road from Kathmandu or Pokhara to another town. Watch Dijkstra's algorithm settle the nearest town first, try the roads out of it, and keep the shortest distance it has found to every town.
Core concept
Dijkstra's algorithm settles towns in order of their distance from the start; each settled town's distance is final, and trying the roads out of it can only make the other towns' distances shorter
Topic: Algorithms
A map of towns joined by roads is a graph: the towns are its nodes and the roads its edges, each with a length. Phone maps find the shortest route with an idea from Edsger Dijkstra. The start is 0 km away and every other town is ∞ (not reached yet). In each round, the program settles the unsettled town with the smallest known distance: that distance can never get shorter, because every other way would have to go through a town that is already farther away. Then it tries each road out of the settled town: if going through it gives a neighbour a shorter distance than the one known, the shorter one replaces it. When the destination is settled, its distance is the shortest, and following back the towns that gave it shows the route. The distances in this lab are rounded road distances, simplified for the map.
What you will learn
- Describe a road map as a graph of nodes and weighted edges.
- Trace Dijkstra's algorithm: settle the nearest town, then try its roads.
- Explain why a settled town's distance is final.
- Show that the route with the fewest roads is not always the shortest.
Before you start
- Know how to add distances and compare which is smaller.
Materials
- A map of Nepal, if you have one
Equipment
- None
Procedure
- Find the shortest route from Kathmandu to Pokhara.
- Find the shortest route from Kathmandu to Butwal, stepping through each round.
- Try other towns, and start from Pokhara.
- Answer the practice challenges.
How this simulation is simplified
- Road distances are rounded and simplified: each road joins two towns directly, and roads go both ways.