Shortest path problems in networks for HSC Maths Standard 2

What this dot point is asking

NESA wants you to find the shortest path between two named vertices in a weighted network. For small networks, inspection is enough: list all the reasonable paths and pick the smallest total. For larger ones, a systematic labelling method (Dijkstra's algorithm) is expected. Once a graph has more than a handful of vertices, this is the method markers prefer to see.

"Shortest" means smallest total weight, whatever the weight represents: distance in km, drive time in minutes, or cost in dollars. The method is identical in each case; only the units change.

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 route built from several small-weight edges can beat a direct route across one large-weight edge, which is exactly why the diagram above takes three edges ($A$-$B$-$C$-$D$, total $6$) rather than the two-edge route $A$-$C$-$D$, which totals $7$.

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 every reasonable path visually.

The risk with inspection is missing a path, so be systematic: fix the first step out of the start vertex, exhaust every route that begins that way, then move to the next first step. A path should never revisit a vertex, because looping back only adds weight and can never shorten a route.

Method 2: systematic labelling (Dijkstra's algorithm)

For larger networks, use systematic labelling. The idea is to give every vertex a running label equal to the shortest distance found so far from the start, then lock in (finalise) vertices one at a time in increasing order of distance:

1. Label the start vertex with $0$. Label all other vertices with $\infty$ (or just "unknown").
2. From the current vertex, look at each neighbour and compute the proposed label as current label + edge weight. If this is less than the neighbour's current label, update it (and record the predecessor).
3. Mark the current vertex as finalised; its label will not change again.
4. Move to the unfinalised vertex with the smallest current label.
5. Repeat steps 2 to 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.

Why do you always finalise (lock in) the smallest unfinalised label? Because nothing left in the graph can reach it for less. Any other route to it would first pass through a vertex whose label is the same or bigger. All the edge weights are positive, so going that way can only add more. That is why a locked-in label never needs to change again.

Tracking the path

While labelling, record the predecessor: which vertex you came from when you set (or last improved) 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. Without the predecessors you get the shortest distance but cannot name the shortest route, and most questions ask for both.

Find the shortest path, stage by stage

The diagram below is run one settled vertex at a time, so you can see exactly where every label comes from. The network has vertices $A$ to $E$; we want the shortest path from $A$ to $E$. Each vertex carries its running shortest distance from $A$ (the start). A vertex with an accent ring has been settled: its label is final and will not change.

Stage 1, settle the start and label its neighbours. Set $A = 0$ and settle it. Look at the edges leaving $A$: $A$-$B$ has weight $2$, so $B$ gets the tentative label $2$; $A$-$C$ has weight $4$, so $C$ gets $4$. Vertices $D$ and $E$ are not yet reachable, so they stay at $\infty$.

Stage 2, settle the smallest label and relax its neighbours. The smallest unfinalised label is $B = 2$, so settle $B$. Now check $B$'s neighbours. The route to $C$ via $B$ is $2 + 1 = 3$, which beats $C$'s current $4$, so update $C$ to $3$ (its predecessor becomes $B$). The route to $D$ via $B$ is $2 + 7 = 9$, so $D$ becomes $9$. This relaxation step, replacing a label when a shorter route appears, is the heart of the method.

Stage 3, settle C, then settle D. The smallest unfinalised label is now $C = 3$, so settle $C$. From $C$: the route to $D$ is $3 + 3 = 6$, beating $D$'s current $9$, so update $D$ to $6$; the route to $E$ is $3 + 5 = 8$, so $E$ becomes $8$. The next smallest unfinalised label is $D = 6$, so settle it; the route $D$-$E$ would give $6 + 2 = 8$, which ties $E$'s existing $8$, so $E$ stays at $8$ (we keep the route already recorded).

Stage 4, settle the end vertex and trace the path back. The only label left is $E = 8$, so settle it; the algorithm is done. Now trace back using predecessors: $E$ was set from $C$ ($3 + 5 = 8$), $C$ was set from $B$ ($2 + 1 = 3$), and $B$ came from $A$. Reversed, the shortest path is $A$-$B$-$C$-$E$ with total $2 + 1 + 5 = 8$. Note the tie spotted in stage 3: the route $A$-$B$-$C$-$D$-$E$ also totals $2 + 1 + 3 + 2 = 8$, so there are two equally short paths.

Laid out as a running table, the four stages are:

A bold entry is a settled (final) label. Reading down a column shows how a vertex's label can fall (for example $C$ drops from $4$ to $3$, and $D$ from $9$ to $6$) but never rises, and never changes once bold.

Equal-weight ties

If two paths have the same total weight, there are multiple shortest paths, and the run above is a clean example: $A$-$B$-$C$-$E$ and $A$-$B$-$C$-$D$-$E$ both total $8$. Systematic labelling reports only one of them (whichever it recorded first), so a tie is easy to miss. When a question asks for "the" shortest path and a tie exists, state every tied route; when it asks only for the shortest distance, the single value $8$ is enough. The tell-tale sign of a tie is the moment in stage 3 where the route $D$-$E$ re-derives $E$'s existing label exactly rather than beating it.

Checking you have not missed a shorter route

The most common worry with inspection is "could there be a shorter path I did not list?" Three checks settle it:

• Cross-check inspection against labelling. If a small graph gives the same answer by both methods, you can be confident. The worked example below does exactly this.
• Confirm the total equals the end label. The summed weights along your chosen path must equal the final label on the end vertex. If they disagree, you have either mis-added or mis-traced the predecessors.
• Confirm every cheaper first move was explored. A shorter route would have to leave the start along a cheaper edge or reach the end through a vertex with a smaller settled label. Because labelling settles vertices in increasing order, anything cheaper was already locked in earlier, so nothing shorter can remain.

Directed versus undirected edges

In Standard 2, road and transport networks are usually undirected. That means an edge between $X$ and $Y$ can be travelled either way for the same weight, so $X$-$Y$ and $Y$-$X$ cost the same. Sometimes a question uses directed edges, which are edges with arrows. A one-way street is one example, or a route where the uphill and downhill times differ. The method does not change, but there is one extra rule: when you update a vertex's neighbours, only follow edges the way their arrow points. On a directed graph, the shortest path from $A$ to $E$ may differ from the shortest path from $E$ to $A$. So read the arrows before you start, and keep to them the whole way through.

Sanity checks

• Total weight on the path equals the final label on the end vertex.
• Each edge used is an actual edge in the graph (and, if directed, used the right way).
• The path is connected: each consecutive pair of vertices is joined by an edge.
• No vertex is visited twice; a repeat means a loop has crept in.

How exam questions ask about shortest paths

The wording varies, but every version reduces to the same task. Learn to translate it:

• "Find the shortest path / shortest route from $X$ to $Y$." Give the path as a sequence of vertices and its total weight with units. The route, not just the number, is required.
• "Find the shortest distance / least time / cheapest cost from $X$ to $Y$." The total weight is the headline answer; still show the route as method.
• "Show your working", or a $4$-plus mark question on a larger graph. Use systematic labelling and show the labels (a running table is ideal); inspection without working can lose method marks once the graph is non-trivial.
• "Is there more than one shortest path?" A tie question: list every route that achieves the minimum total.
• "Explain why this route is shortest." Point to the labelling: the end vertex was settled at that value, and no unsettled vertex had a smaller label, so no shorter route exists.
• "One road is closed, or a new road opens." Re-run the affected part: delete or add the edge, then recompute. Often only one or two labels change.

One distinction is worth a mark. A question that says "connect all the towns with the least total road length" is a minimum spanning tree problem, not a shortest path. A shortest path runs point to point between two named vertices. A minimum spanning tree (MST) instead joins up every vertex. Decide which one is being asked before you start.