How a map app finds the shortest route
Tonight's idea
A map app cannot try every route: there are far too many. It uses a method found by the Dutch computer scientist Edsger Dijkstra in the 1950s.
Give every place a label: the shortest distance from the start found so far. The start gets 0. The rest get \(\infty\), meaning "no route yet". Then repeat two steps.
1. Of the places not yet settled, pick the one with the smallest label. Settle it: that label is final.
2. For each road from it to an unsettled place, add the road's length to its label. If the total beats that place's label, replace the label.
Stop when the destination is settled.
Why is the smallest label final? Any other route to that place must leave the settled places somewhere. Its first stop outside them is an unsettled place whose label is already at least as big. The rest of the route can only add length, because no road is shorter than zero. So no detour can win, and the method never has to go back.
Watch one: from A to F
| Settle | Label | Roads out of it |
|---|---|---|
| A | 0 | B gets 4. C gets 2. |
| C | 2 | B: \(2 + 1 = 3\), beats 4. E gets \(2 + 7 = 9\). |
| B | 3 | D gets \(3 + 5 = 8\). |
| D | 8 | E: \(8 + 2 = 10\), no: 9 stays. F gets \(8 + 6 = 14\). |
| E | 9 | F: \(9 + 3 = 12\), beats 14. |
| F | 12 | Done. |
The shortest distance from A to F is 12 km. For the route, trace back who gave each final label: F got 12 from E, E got 9 from C, C got 2 from A. The route is A–C–E–F.
Tap a start and an end, then press Step to settle one town at a time and watch the labels change: mathdetours.com/demos/dijkstra.html.
Your turn
All four questions use the map above.
- A friend has a simpler rule: from where you stand, always take the shortest road to a place you have not visited. (a) Follow it from A until you reach F. Which route, and how long? (b) At which place did the rule make its mistake?
- Run Dijkstra's method starting from F. Write down the final label of every place, in the order you settle them. What is the shortest route from F to A?
- The road C–E is closed. Start from A again. (a) Which labels stay the same, and why? (b) Find the new shortest distance and route to F.
- With every road open, a new road is built straight from A to D, a whole number of km long. How long can it be and still make the trip from A to F shorter than 12 km? Say which route the trip then takes.
Stretch: a road that pays you
Three places. A–B is 2, A–C is 3, and C–B is \(-2\): a road that pays you back. Run Dijkstra's method from A. With what label is B settled? What is the true shortest distance to B? Which sentence of the argument has failed?
Answers
- (a) A–C (2), C–B (1), B–D (5), D–E (2), E–F (3): the route A–C–B–D–E–F, 13 km. (b) At C. The 1 km road to B looked better than the 7 km road to E, but it led to a longer trip. A short next step says nothing about the whole route. Dijkstra's labels measure the whole distance from the start.
- F 0, E 3, D 5 (via E, beating the direct 6), then B 10 and C 10 in either order, then A 12. B is reached through D (\(5 + 5\)) and C through E (\(3 + 7\)). A gets \(10 + 2 = 12\) from C, beating \(10 + 4 = 14\) from B. Route F–E–C–A, the earlier route backwards.
- (a) B (3), C (2) and D (8) stay the same: their shortest routes never used C–E. (b) E can now only be reached through D: \(8 + 2 = 10\). F is \(10 + 3 = 13\), beating \(8 + 6 = 14\). Route A–C–B–D–E–F, 13 km.
- Call the new road \(x\) km. From D the best way on is D–E–F, \(2 + 3 = 5\) km, not D–F, which is 6. So the trip is \(x + 5\), and \(x + 5 \lt 12\) when \(x \lt 7\). The road can be up to 6 km long, and the route is A–D–E–F.
Stretch. Labels after settling A: B 2, C 3. B has the smallest label, so it is settled with 2. But A–C–B is \(3 - 2 = 1\). The sentence "the rest of the route can only add length" failed: a negative road lets a detour through an unsettled place come out shorter. Dijkstra's method needs every length to be zero or more.