Lesson 6 of 8 · 15 min
Shortest paths by trial and error
Find the shortest path between two vertices of a weighted graph by listing the possible routes systematically, totalling each, and choosing the least.
What you will be able to do
- Explain what the shortest path between two vertices of a weighted graph is.
- List the possible routes between two vertices systematically.
- Find the shortest path and its length by trial and error, and state it clearly.
- Interpret weights as distances, times or costs.
Two roads climb from Cairns to the Atherton Tableland: the Kuranda Range road through Kuranda and Mareeba, and the Gillies Range road through Gordonvale and Yungaburra. Which way is shorter to Atherton?
On a map it is hard to tell. On a weighted graph you can settle it by adding.
Definition
Shortest path
In a weighted graph, the length of a route is the sum of the weights of its edges. The shortest path between two vertices is the route with the least total weight. The weights might be distances, travel times or costs — "shortest" always means least total weight.
Approximate road distances in kilometres. Try a few routes from Cairns to Atherton and add up their distances. Which is shortest?
Finding a shortest path by trial and error
Branch from the start
List the vertices you can reach from the start. Follow each branch in turn, never returning to a vertex already on the route.
Follow each branch to the finish
Write down each complete route and its running total as you go.
Abandon hopeless routes
Once a part-route already totals more than the best complete route so far, stop following it.
Compare and state
Give the shortest route as a sequence of vertices, with its total and units.
Worked example
Shortest route from Cairns to Atherton
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. ✓
Try it yourself first, then check the working one step at a time.
Answer
Cairns–Gordonvale–Yungaburra–Atherton, 79 km.
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.
Using the road network in the example above, find the length of the shortest route from Kuranda to Yungaburra, in kilometres.
Tip
Look for detours that beat a direct edge
A heavy edge can often be beaten by going around it. In the next example, to directly costs 4, but –– costs only .
Worked example
When the shortest path uses more edges
Find the shortest path from to in the weighted graph, and its length.
Step 1: Spot the light and heavy edges
The light edges are , and , so good routes probably use them. The heavy edge is worth avoiding.
This is the "trial" in trial and error: aim your first tries at light edges, then check the alternatives.
Step 2: Get from A to B cheaply
Direct, – costs 4, but –– costs .
Step 3: Get from D to F cheaply
Direct, – costs 6, but –– costs .
Step 4: Compare the complete routes
- –––:
- –––:
- ––––:
- ––––:
- –––––:
The other routes use with a detour, and total 18 or more.
Step 5: State the shortest path
The shortest path is –––––, with length 13. It uses five edges, while both three-edge routes total 15.
Try it yourself first, then check the working one step at a time.
Answer
–––––, with length 13.
Method
Look for light edges and short detours that beat a heavy direct edge.
List the candidate routes and total each one.
Choose the least total, even if it uses more edges.
Watch out for
Choosing ––– because it looks the most direct. It totals 15.
In the graph of the example above, which route is the shortest path from to ?
Note
Distance or time?
If the weights are travel times, the shortest path is the quickest route, and it need not be the shortest distance. The Gillies Range road is the shorter way from Cairns to Atherton, but it is famously winding, so it is not necessarily the quicker one. Always check what the weights measure.
Common mistake
Choosing by the number of edges
The route with the fewest edges is not necessarily the shortest. Total the weights of every route you consider before deciding.
Exam tip
"By trial and error" still needs visible working. List the routes you compared with their totals, then state the shortest route as a vertex sequence with its length and units. A bare answer can lose the method marks.
Summary
The length of a route is the sum of its edge weights; the shortest path has the least total weight.
List routes systematically by branching from the start, and never revisit a vertex.
Abandon any part-route that is already longer than the best complete route.
A route with more edges can be shorter — total the weights, do not count the edges.
State the route, its total and its units. Check what the weights measure.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.