Lesson 6: Shortest paths by trial and error
Shortest route from Cairns to Atherton
SkillShortest paths by trial and error
Worked example
The network shows approximate road distances, in kilometres, between towns near Cairns. Find the shortest route from Cairns to Atherton, and its length.
Step 1: List the routes that do not revisit a town
Leaving Cairns you must go to Kuranda or Gordonvale, so the routes are:
- Cairns–Kuranda–Mareeba–Atherton
- Cairns–Gordonvale–Yungaburra–Atherton
- Cairns–Gordonvale–Yungaburra–Malanda–Atherton
A shortest route never visits a town twice, so you only need to list paths.
Step 2: Total each route
- Via Kuranda: km
- Via Gordonvale and Yungaburra: km
- Via Gordonvale, Yungaburra and Malanda: km
Step 3: Choose the least total
The shortest route is Cairns–Gordonvale–Yungaburra–Atherton, 79 km.
Step 4: Check it is reasonable
The 99 km route is the 79 km route with a detour through Malanda in place of the direct 13 km road, so it had to be longer. ✓
Answer
Cairns–Gordonvale–Yungaburra–Atherton, 79 km.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
List the paths from the start to the finish systematically, branching at each vertex.
Total the weights along each path.
Choose the least total, and state the route and its length with units.
Watch out for
Stopping after the first route you find. The fewest towns is not always the shortest distance.