What is not updating a label?

A route through an intermediate vertex may beat a direct edge; always keep the smaller running total.

§-Syllabus dot point

WAMathematics ApplicationsSyllabus dot point

How do we find the route of least total weight between two points in a network?

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

How to find the shortest path between two vertices in a weighted network by systematic listing or labelling, interpret the result, and tell shortest path apart from minimum spanning tree.

Generated by Claude Opus 4.87 min answerUpdated 2026-06-02

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

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

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

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.

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.

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.

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.

Exam-style practice questions

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

WACE 20226 marksIn 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 20244 marksExplain 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.