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.

Interactive

Cairns to Atherton

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

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

  2. Follow each branch to the finish

    Write down each complete route and its running total as you go.

  3. Abandon hopeless routes

    Once a part-route already totals more than the best complete route so far, stop following it.

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

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

4 steps

Try it yourself first, then check the working one step at a time.

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.

Using the road network in the example above, find the length of the shortest route from Kuranda to Yungaburra, in kilometres.

in km

Tip

Look for detours that beat a direct edge

A heavy edge can often be beaten by going around it. In the next example, AA to BB directly costs 4, but AA–CC–BB costs only 2+1=32 + 1 = 3.

Worked example

When the shortest path uses more edges

  • Complex familiar

Find the shortest path from AA to FF in the weighted graph, and its length.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Look for light edges and short detours that beat a heavy direct edge.

  2. List the candidate routes and total each one.

  3. Choose the least total, even if it uses more edges.

Watch out for

  • Choosing AA–BB–DD–FF because it looks the most direct. It totals 15.

In the graph of the example above, which route is the shortest path from AA to DD?

Choose one answer

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.

Lesson 6 of 80% read

Save your progress with a free account