QLDGeneral MathematicsSyllabus dot point

Topic 3: Networks and decision mathematics - how do we find the cheapest or quickest route between two points in a network?

Find the shortest path between two vertices in a weighted network by inspection and by systematic labelling, distinguish the shortest path from the minimum spanning tree, and apply shortest-path methods to travel-time and cost problems

A focused answer to the QCE General Mathematics Unit 4 dot point on shortest paths. Covers finding the shortest route between two vertices in a weighted network by inspection and systematic labelling, how the shortest path differs from a minimum spanning tree, and travel-time and cost applications, with arithmetic-verified worked examples for IA3 and the external assessment.

Generated by Claude Opus 4.76 min answerUpdated 2026-05-29

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

What this dot point is asking

QCAA wants you to find the route of least total weight between two specified vertices in a weighted network, where the weights are distances, times or costs. You do this by inspection on small networks and by a systematic labelling method on larger ones, and you must keep it distinct from the minimum spanning tree, which connects everything rather than linking two points. This is a separate sub-topic of Unit 4 Topic 3 and appears regularly in IA3 and the external assessment.

The answer

What the shortest path means

The shortest path between a start vertex and an end vertex is the sequence of edges joining them with the smallest total weight. "Shortest" can mean least distance, least time or least cost depending on what the weights represent. There may be more than one path of equal least weight.

Finding it by inspection

On a small network you list the sensible routes from start to finish, add the edge weights along each, and pick the smallest total. This works when there are only a handful of paths, and it is often the fastest method in an exam if the network is simple. The trap is missing a route, so be systematic about listing them.

The systematic labelling method

On a larger network you label each vertex with the smallest total weight needed to reach it from the start. Begin by labelling the start vertex $0$ . Then repeatedly take the vertex with the smallest confirmed label and update each of its neighbours: a neighbour's working value is the current vertex's label plus the connecting edge weight, and you keep the smallest working value found for each vertex. Once a vertex has the smallest unconfirmed label it is confirmed and never changes. The label on the destination is the shortest distance, and you trace the path back through the edges that produced each confirmed label.

Shortest path versus minimum spanning tree

These are easy to confuse. The minimum spanning tree connects every vertex at least total cost; the shortest path connects just two chosen vertices at least cost. The edges in the shortest path need not appear in the minimum spanning tree, and vice versa. Read the question to see whether it asks to connect everything (spanning tree) or to travel between two points (shortest path).

Common traps

Missing a route in the inspection method: If you skip a possible path you may miss the true shortest. List routes systematically, including ones that double back through cheap edges.
Confirming a vertex label too early: In the labelling method a vertex is only confirmed once it has the smallest unconfirmed label. Confirming a larger label first can lock in a non-shortest distance.
Confusing shortest path with minimum spanning tree: A spanning tree connects all vertices; a shortest path links two. Using one method when the question wants the other loses the marks.
Adding the wrong edges when tracing back: The path is reconstructed from the edges that set each confirmed label. Tracing through arbitrary edges can give a path whose total does not match the destination label.
Assuming the direct edge is shortest: A single direct edge between two vertices is often not the shortest path; a detour through cheaper edges can beat it, as in the worked example.

Exam-style practice questions

Practice questions written in the style of QCAA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

2022 QCAA5 marksThe table shows the current road length (in kilometres) between six towns (Manon, Veria, Bolint, Farra, Recen, Alin). The connections include Manon-Veria 16, Manon-Bolint 34, Manon-Alin 33, Veria-Bolint 12, Veria-Recen 15, Bolint-Recen 10, Farra-Recen 15, Farra-Alin 23, Recen-Alin 15. The government plans to build a direct road between Manon and Farra. Use a network diagram to determine the length of the direct road if it is to be 4 km shorter than the length of the current shortest road route between Manon and Farra.

Show worked answer →

Step 1 - draw the network (1 mark). Represent the six towns as vertices and the given road lengths as weighted edges.

Step 2 - include the lengths (1 mark). Label every edge with its kilometre distance so the routes can be compared.

Step 3 - find the shortest route from Manon to Farra (1 mark). Checking the candidate routes, Manon - Veria - Bolint - Recen - Farra has length 16 + 12 + 10 + 15 = 53 km, which is the shortest. (Routes through Alin, such as Manon - Alin - Farra = 33 + 23 = 56, are longer.)

Step 4 - state the shortest distance (1 mark): the current shortest road route is 53 km.

Step 5 - find the new road length (1 mark): the direct road is 4 km shorter, so 53 - 4 = 49 km.

The shortest path is the least-weight route between just these two towns; unlike a minimum spanning tree it does not need to reach every town, only Manon and Farra.