Shortest path problems in WACE Mathematics Applications Unit 4

Syllabus dot point

“Find the shortest path between two vertices in a weighted network and interpret it in context.”

WACEMathematics ApplicationsUnit 47 min readUpdated 2 Jun 2026

Quick answer

A shortest path problem finds the route of least total weight (distance, time or cost) between two named vertices in a weighted network. Solve it by labelling each vertex with the smallest running total from the start, updating a label whenever a shorter route to that vertex is found, until the destination carries its least possible label. A shortest path is a single journey, not the whole-network connection of a minimum spanning tree.

Jump to a section

What this dot point is asking
Shortest path versus spanning tree
Finding the shortest path
Directed networks and one-way edges
Interpreting the result
Exam-style questions

What this dot point is asking

You must find the shortest path between two vertices and interpret it in context.

Shortest path versus spanning tree

These two network problems are easy to confuse, but they answer different questions.

Shortest path versus minimum spanning tree

A shortest path is the route of least total weight between two specific vertices. A minimum spanning tree is the least-weight set of edges that connects all vertices. The first is one journey; the second links everything. They generally use different edges.

Read the wording: "travel from $A$ to $E$ ", "quickest route", "least cost from start to finish" signal a shortest path; "connect all sites", "least cabling for the whole network" signal a spanning tree.

Finding the shortest path

For the small networks in this course, a systematic labelling method works reliably.

Shortest-path labelling method

Label the start vertex with $0$ .
For every other vertex, find the smallest total distance from the start along any route reaching it so far, and record it as the vertex's label.
Whenever a new route gives a smaller total to a vertex, update its label to the smaller value.
Continue until the destination has its smallest possible label; that is the shortest distance, and tracing back the chosen edges gives the path.

The crucial step is updating: a route through an intermediate vertex can be shorter than a direct edge, so always compare and keep the smaller total.

Always keep the smaller running total

At each vertex, the label is the least distance from the start found so far. If a different route arrives with a smaller total, replace the label. Forgetting to update is the main reason for a wrong shortest path.

Worked example

Finding a shortest path

A delivery network has distances $S\to A = 6$ , $S\to B = 2$ , $A\to C = 3$ , $B\to A = 3$ , $B\to C = 9$ , $C\to T = 4$ , $A\to T = 11$ . Find the shortest path from $S$ to $T$ .

Step 1: Label the start vertex and record direct distances from S.

We assign $S$ the label $0$ , because zero distance has been travelled at the start. From $S$ we can reach $A$ directly in $6$ and $B$ directly in $2$ , so $A$ is tentatively labelled $6$ and $B$ is labelled $2$ . These are the best distances we have found so far.

Step 2: Update labels via intermediate vertices.

Routing through an intermediate vertex can yield a shorter total distance than travelling directly, so we always check every route and keep the smallest running total. To reach $A$ : the direct route from $S$ costs $6$ , but going via $B$ costs $2 + 3 = 5$ , which is smaller. We update $A$ 's label to $5$ . To reach $C$ : via $A$ is $5 + 3 = 8$ ; via $B$ is $2 + 9 = 11$ . The smaller is $8$ , so $C$ is labelled $8$ .

Step 3: Find the shortest distance to the destination T.

With all intermediate labels settled, we compare every route that arrives at $T$ . Via $C$ : $8 + 4 = 12$ . Via $A$ directly: $5 + 11 = 16$ . The smaller total is $12$ , so $T$ receives the final label $12$ .

Step 4: Trace back the path and interpret the result.

We identify the path by following the edges that achieved each smallest label: $S \to B$ (cost $2$ ), then $B \to A$ (cost $3$ , giving the updated label of $5$ for $A$ ), then $A \to C$ (cost $3$ ), then $C \to T$ (cost $4$ ). The shortest path is $S \to B \to A \to C \to T$ , length $2 + 3 + 3 + 4 = 12$ . The delivery van should take this route for the least total distance.

Directed networks and one-way edges

In a directed network the edges have a direction (one-way roads, irreversible processes), so a route may only travel along an edge the way it points. When labelling, only update a vertex from a predecessor that has an edge pointing towards it. A path that would be valid in an undirected network can be impossible in a directed one, so always check the arrow direction before adding an edge to a route. Critical path analysis (scheduling) and flow networks both use directed edges for this reason.

Interpreting the result

State both the path (the sequence of vertices) and its total weight, and interpret in context: the cheapest delivery route, the quickest journey, or the least-cost connection between two points. The shortest path need not use the fewest edges; a longer route through more vertices can have a smaller total weight.

If a question asks for a round trip or for the shortest path that must pass through a particular intermediate vertex, split it into stages: find the shortest path from the start to the required vertex, then from that vertex to the destination, and add the two totals. The overall shortest constrained route is the sum of the shortest sub-paths.

Common errors

Confusing shortest path with minimum spanning tree: A shortest path is one journey between two vertices; a spanning tree connects all vertices.
Not updating a label: A route through an intermediate vertex may beat a direct edge; always keep the smaller running total.
Choosing the path with the fewest edges: Fewest edges is not the same as least total weight; compare totals, not edge counts.
Forgetting to state the route: Report both the sequence of vertices and the total distance, then interpret in context.

Exam-style questions

Questions in the style of SCSA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

WACE 2022-style6 marks

In a road network the distances (km) are

A\to B = 4

A\to C = 2

B\to D = 5

C\to B = 1

C\to D = 8

C\to E = 7

D\to E = 3

. Find the shortest path from

A

E

and its length.

Show worked answer →

Label each vertex with the least distance from the start, updating as shorter routes appear.

From $A$ : to $C$ is $2$ , to $B$ is $4$ . Via $C$ to $B$ is $2 + 1 = 3$ , which beats $4$ , so $B$ is labelled $3$ . To $D$ : via $B$ is $3 + 5 = 8$ , via $C$ is $2 + 8 = 10$ , so $D$ is $8$ . To $E$ : via $C$ directly is $2 + 7 = 9$ ; via $D$ is $8 + 3 = 11$ . The smaller is $9$ . (4 marks)

Shortest path: $A \to C \to E$ , length $2 + 7 = 9$ km. (2 marks)

Markers reward updating $B$ to $3$ via $C$ , comparing the routes to $E$ , and the $9$ km path $A$ - $C$ - $E$ .

WACE 2024-style4 marks

Explain how a shortest path problem differs from a minimum spanning tree problem, and describe how you would systematically find a shortest path between two vertices.

Show worked answer →

One is a single journey; the other connects everything.

A shortest path finds the route of least total weight between two specific vertices. A minimum spanning tree connects all vertices together at least total weight. They answer different questions and usually give different edge sets. (2 marks)

To find a shortest path, label the start vertex $0$ , then repeatedly assign each vertex the smallest running total from the start along any route, updating whenever a shorter route is found, until the destination has its least label. (2 marks)

Markers reward the single-journey versus connect-all distinction and the least-running-total labelling method.