Shortest paths in weighted networks: HSC Maths Standard 1 Year 12
“N1.2 Shortest paths: find the shortest path between two vertices in a weighted network by inspection or by a systematic method, recognising that there may be more than one shortest path, and solve practical problems involving shortest paths”
The shortest path between two vertices is the route with the smallest total weight (distance, time or cost), not necessarily the fewest edges. Find it by inspection for small networks or by labelling each vertex with its smallest total from the start and tracing back, and remember there may be more than one shortest path.
Jump to a section
What this dot point is asking
You need to find the shortest path between two vertices in a weighted network and solve practical problems with it (quickest delivery route, cheapest connection, shortest road trip). NESA's topic guide notes that there are often several shortest paths of equal length.
The answer
By inspection
For small networks, list the reasonable paths from start to finish, add their weights, and choose the smallest total. Check routes that use more edges: they can be shorter.
A systematic labelling method
For larger networks:
- Label the start vertex 0.
- Label each neighbouring vertex with the distance from the start.
- Move outward: for each vertex, the label is the smallest total of (label of a connected vertex + edge weight).
- Update a label if you find a shorter route.
- When the finish is labelled, trace back through the vertices whose labels produced it.
- The shortest path minimises total weight, not the number of edges.
- There may be more than one shortest path.
- The weight can be distance, time or cost, so the "shortest" route depends on what is measured.
Towns and road distances (km): W to X 12, W to Y 7, Y to X 4, X to Z 9, Y to Z 15.
- W = 0.
- Y = 7 (W to Y). X = minimum of 12 and , so 11.
- Z = minimum of and , so 20.
- Trace back: Z from X, X from Y, Y from W.
Shortest path: W to Y to X to Z, 20 km.
Choosing the path with fewest edges. Always compare total weights.
Not updating labels when a shorter route is found.
Forgetting to trace the path. Give the route, not just the total.
Practice questions
Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.
foundation3 marksIn a road network, the distances (km) are: A to B 6, A to C 4, B to D 5, C to D 9, C to B 1. Find the shortest path from A to D.Show worked solution →
Paths from A to D:
- A to B to D: km
- A to C to D: km
- A to C to B to D: km
Shortest path: A to C to B to D, 10 km.
Marking guide: 1 mark for listing paths, 1 mark for correct totals, 1 mark for the shortest path.
core4 marksTravel times (minutes) between delivery stops are: Depot to P 8, Depot to Q 5, P to R 7, Q to P 2, Q to R 12, R to S 4, P to S 13. Use labelling to find the quickest route from the Depot to S.Show worked solution →
- Depot: 0.
- Q: 5 (Depot to Q).
- P: minimum of 8 (direct) and (via Q), so 7.
- R: minimum of (via P) and (via Q), so 14.
- S: minimum of (via R) and (via P), so 18.
Trace back: S from R, R from P, P from Q, Q from Depot.
Quickest route: Depot to Q to P to R to S, 18 minutes.
Marking guide: 1 mark per correctly labelled vertex (P, R, S), 1 mark for the route.
exam4 marksA cyclist wants the shortest route between two towns and finds two routes of 34 km. Explain why both are shortest paths, and suggest another factor that might decide which route to take.Show worked solution →
A shortest path is any path with the smallest total weight. If two different routes both total 34 km and no route is shorter, both are shortest paths; networks can have more than one.
Other factors: hills and elevation gain, traffic and safety, road surface (sealed or gravel), bike lanes, or places to stop for water. The network weight here only measures distance, so the cyclist might choose the flatter or safer route.
Marking guide: 2 marks for explaining equal shortest paths, 2 marks for relevant other factors linked to the limitation of the weight used.