NSWMaths Standard 2Syllabus dot point

How is the shortest path between two vertices in a weighted network found?

Find the shortest path between two vertices in a weighted network by inspection or by systematic labelling

A focused answer to the HSC Maths Standard 2 dot point on shortest paths. Inspection method for small networks, systematic labelling for larger ones, and worked examples for road network distances and Sydney transport routes.

Generated by Claude OpusReviewed by Better Tuition Academy7 min answerUpdated 2026-05-20

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

What this dot point is asking

NESA wants you to find the shortest path between two specified vertices in a weighted network. For small networks, inspection (listing all reasonable paths and picking the smallest) is enough. For larger ones, a systematic labelling method like Dijkstra's algorithm is expected.

The answer

What the question asks

Given a weighted graph with vertices and edge weights (distances, times, costs), find the path from a starting vertex to an ending vertex with the smallest total weight.

The shortest path may not be the path with the fewest edges. A long edge with low weight per edge can sometimes be faster than a short path with high weights.

Method 1: inspection

For small networks (say $5$ vertices or fewer), list all sensible candidate paths between the start and end vertex, compute each total weight, and pick the smallest.

This works when:

The graph is small.
There are few branching options.
You can spot all reasonable paths visually.

Method 2: systematic labelling (Dijkstra's algorithm)

For larger networks, use systematic labelling:

Label the start vertex with $0$ . Label all other vertices with $\infty$ (or just "unknown").
From the current vertex (start with the start), look at each neighbour and compute the proposed label = current label + edge weight. If this is less than the neighbour's current label, update.
Mark the current vertex as finalised.
Move to the unfinalised vertex with the smallest current label.
Repeat steps 2-4 until the end vertex is finalised.

The final label on the end vertex is the shortest total weight. Trace back through the predecessors to find the actual path.

Tracking the path

While labelling, record the predecessor: which vertex you came from when you set the current label. After finishing, trace backwards from the end vertex to the start using these predecessors, then reverse to get the path in forward order.

Equal-weight ties

If two paths have the same total weight, there are multiple shortest paths. State both (or all) in your answer.

Sanity checks

Total weight on the path equals the final label on the end vertex.
Each edge used was an actual edge in the graph.
The path is connected: each consecutive pair of vertices is joined by an edge.

Worked example

Inspection on a small graph

Graph with $4$ vertices and weighted edges:

Edge	Weight (km)
IMATH_1 - IMATH_2	IMATH_3
IMATH_4 - IMATH_5	IMATH_6
IMATH_7 - IMATH_8	IMATH_9
IMATH_10 - IMATH_11	IMATH_12
IMATH_13 - IMATH_14	IMATH_15

Shortest $A$ to $D$ ?

Candidate paths:

IMATH_18 - $B$ - $D$ : $3 + 6 = 9$ .
IMATH_22 - $C$ - $D$ : $5 + 2 = 7$ .
IMATH_26 - $B$ - $C$ - $D$ : $3 + 1 + 2 = 6$ .
IMATH_31 - $C$ - $B$ - $D$ : $5 + 1 + 6 = 12$ .

Shortest: $A$ - $B$ - $C$ - $D$ with total $6$ km.

Systematic labelling

Starting from $A$ . Label $A = 0$ . Others $\infty$ .

From $A$ : update $B = 3$ , $C = 5$ . Finalise $A$ .

Smallest unfinalised label: $B = 3$ . From $B$ : $C = \min(5, 3 + 1) = 4$ . $D = 3 + 6 = 9$ . Finalise $B$ .

Smallest unfinalised: $C = 4$ . From $C$ : $D = \min(9, 4 + 2) = 6$ . Finalise $C$ .

Smallest unfinalised: $D = 6$ . Finalise $D$ . Done.

Shortest distance $A$ to $D$ : $6$ km. Trace back: $D$ came from $C$ (because $4 + 2 = 6$ ), $C$ came from $B$ (because $3 + 1 = 4$ ), $B$ came from $A$ (because $0 + 3 = 3$ ). Path: $A$ - $B$ - $C$ - $D$ .

Australian transport context

Suppose Sydney transport edges (in minutes):

Wynyard to Town Hall: $3$
Town Hall to Central: $3$
Wynyard to Martin Place: $4$
Martin Place to St James: $3$
St James to Museum: $2$
Museum to Central: IMATH_80

Shortest Wynyard to Central?

Path 1: Wynyard-Town Hall-Central: $3 + 3 = 6$ minutes.

Path 2: Wynyard-Martin Place-St James-Museum-Central: $4 + 3 + 2 + 4 = 13$ minutes.

Shortest: Path 1 at $6$ minutes.

A real Sydney commute usually uses Path 1 (the City Circle direct route), exactly because it has the lowest total time.

Past exam questions, worked

Real questions from past NESA papers on this dot point, with our answer explainer.

2022 HSC Q244 marksIn a road network with vertices

A, B, C, D, E

and weighted edges representing distances in km, find the shortest path from

A

E

and state its length.

Show worked answer →

List all possible paths from $A$ to $E$ and their lengths.

Say the paths are: $A$ - $B$ - $E$ (length $4 + 8 = 12$ ), $A$ - $C$ - $E$ (length $5 + 6 = 11$ ), $A$ - $C$ - $D$ - $E$ (length $5 + 3 + 2 = 10$ ), $A$ - $B$ - $D$ - $E$ (length $4 + 4 + 2 = 10$ ).

The shortest is $10$ km, via either $A$ - $C$ - $D$ - $E$ or $A$ - $B$ - $D$ - $E$ (both give the same length).

Markers reward listing the candidate paths systematically, computing each total, identifying the shortest, and noting if multiple paths tie. State all tied shortest paths if asked.

2023 HSC Q234 marksA driver in Sydney wants the shortest route from her home (vertex

H

) to her workplace (vertex

W

) using a weighted graph where edges are road segments and weights are typical drive times in minutes. Find the shortest route and its total time.

Show worked answer →

Apply systematic labelling: starting at $H$ , label each vertex with the shortest known total time from $H$ . Update labels as shorter paths are found.

Step through: label $H$ with $0$ . Label its neighbours with the edge weights to them. From the next vertex with the smallest label, update its neighbours, and so on, always taking the smallest unfinalised label next.

Continue until $W$ is labelled. The final label on $W$ is the shortest total time. Trace back via the predecessors to find the actual route.

Markers reward systematic application of the labelling, accurate intermediate values, the shortest time, and the route traced back. State the route as a sequence of vertices and the total time with units.