Lesson 6: Shortest paths by trial and error

Shortest route from Cairns to Atherton

SkillShortest paths by trial and error

Worked example

  • Simple familiar

The network shows approximate road distances, in kilometres, between towns near Cairns. Find the shortest route from Cairns to Atherton, and its length.

1 of 4 steps
  1. 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

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. List the paths from the start to the finish systematically, branching at each vertex.

  2. Total the weights along each path.

  3. 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.

Save your progress with a free account