Shortest path problems (QCE General Mathematics Unit 4)
“Solve practical problems to determine the shortest path between two vertices in a weighted graph by trial-and-error methods, distinguishing the shortest path from a minimum spanning tree”
A shortest path is the least-weight route between two specified vertices. The QCAA syllabus uses trial and error: systematically list every route that does not revisit a vertex, keep running totals, prune any partial route already longer than the best found, and choose the smallest total (checking for ties). Handle required stops by adding two shortest paths, closures and new roads by searching again, and speeds by converting to times; do not confuse it with a minimum spanning tree.
Jump to a section
What this dot point is asking
A shortest path is the route of least total weight between two chosen vertices of a weighted graph. "Shortest" means whatever the weights measure: least distance, least time or least cost. The QCAA General Mathematics 2025 syllabus asks you to solve practical problems to determine the shortest path between two vertices in a weighted graph, by trial-and-error methods only (Topic 3, Graphs and networks). In practice, "trial and error" means a systematic search through the sensible routes, not random guessing.
Shortest path questions often come wrapped in a practical context: a new road that must be a certain amount shorter than the current best route, a road closure, a stop that must be made on the way, or a choice between a short route and a fast one.
The answer
What counts as a route
Because every weight is positive, a shortest route never needs to visit a vertex twice (going round in a loop only adds weight). So the candidates are the paths from the start to the finish: routes that do not repeat a vertex. On the small networks used in QCAA questions there are usually between 3 and 12 of these.
A systematic trial-and-error search
The risk with trial and error is missing a route. A systematic search avoids that:
- Start at the start vertex. List each edge leaving it as the first step of a route.
- Extend every route one edge at a time, never returning to a vertex already on that route, until it reaches the finish or gets stuck.
- Keep a running total of each route's weight.
- Prune: once you have one complete route, abandon any partial route whose running total already equals or exceeds it, because it can only get longer.
- Compare the complete routes and choose the smallest total. Check for ties.
For the network above, from A to E:
| Route | Running total | Status |
|---|---|---|
| A-B-D-E | complete: best so far | |
| A-B-C-D-E | complete, longer | |
| A-B-D-F-E | before the last road | pruned (already over 46) |
| A-C-... | 30 after one road, then at D, | complete, longer |
| A-F-E | complete, longer | |
| A-F-D-E | at D, | complete, longer |
The shortest path is A-B-D-E, 46 km. The route that "looks" direct on the map, A-F-E, uses only two roads but is 3 km longer.
A shortest path joins two specified vertices with the least total weight. Find it by listing every sensible route (never revisiting a vertex), adding the weights, pruning any partial route that already exceeds the best complete route, and choosing the smallest total. Check for ties, and use the weights (distance, time or cost) that match the question.
A helpful shortcut: best distances to intermediate vertices
While searching, keep note of the shortest distance found so far to each intermediate vertex. In the example, D can be reached by A-B-D (33), A-B-C-D (34), A-C-D (39) or A-F-D (44). Only the best, 33, matters for any route continuing from D, so every route that reaches D more slowly can be abandoned. This idea is the basis of a formal algorithm (Dijkstra's algorithm), which is not required by the QCAA syllabus but works in exactly this spirit.
Practical variations
- A required stop. If the route must pass through vertex X, find the shortest path from the start to X and the shortest path from X to the finish, then add them.
- A road closure. Delete that edge and search again. The new best route may use completely different roads.
- A new road. A new direct road is only useful if it is shorter than the current shortest route. Questions sometimes ask how long a new road must be, for example "4 km shorter than the current shortest route".
- Ties. Two or more routes may share the least total; if asked "how many shortest routes", count them all.
- Distance versus time. If speeds differ on different roads, convert each road to a time () before searching for the quickest route. The shortest route and the quickest route can be different.
Shortest path versus minimum spanning tree
| Shortest path | Minimum spanning tree | |
|---|---|---|
| Joins | two chosen vertices | every vertex |
| Minimises | the length of one route | the total length of all edges used |
| Uses | a single path | a tree with edges |
| Typical question | quickest drive, cheapest delivery route | least cable, pipe or track to connect all sites |
The two problems usually give different sets of edges, so read the question carefully.
A small network
Edges: S-A 2, S-B 4, A-B 1, A-T 7, B-T 3. Find the shortest path from S to T.
List the routes. S-A-T 9; S-B-T 7; S-A-B-T ; S-B-A-T .
Choose. S-A-B-T, 6.
Marker's note: listing every route and its total is what earns the method mark; an answer alone risks nothing to award if it is wrong.
A required stop
Using the six-town network, find the shortest route from A to E that passes through C.
- Start to C
- A-C directly is 30, but A-B-C is . Shortest: 25.
- C to finish
- C-D-E is ; C-B-D-E is . Shortest: 22.
- Total
- km, route A-B-C-D-E.
Marker's note: the required stop adds only 1 km here, because C is almost on the best route anyway.
A new road and a closure
The council builds a direct road A-E that is 4 km shorter than the current shortest route, then closes road B-D. Find the new road's length and the shortest route from B to E after the closure.
New road. Current shortest A to E is 46, so the new road is 42 km.
After closing B-D. From B: B-C-D-E ; B-A-E ; B-C-D-F-E . Shortest: B-C-D-E, 33 km.
Marker's note: when a question changes the network, rewrite the list of edges with the change before searching again.
Quickest versus shortest
Freeway route D-X-C: 40 km at 100 km/h and 12 km at 60 km/h. Town route D-Y-Z-C: 18 km at 50 km/h, 10 km at 40 km/h and 8 km at 60 km/h.
- Distances
- Freeway 52 km, town 36 km.
- Times
- Freeway h (36 min); town h (about 45 min).
- Conclusion
- The town route is shorter but the freeway is quicker.
Marker's note: convert every edge to the same unit (hours or minutes) before adding.
- Missing a route
- Work outward from the start systematically; do not rely on spotting routes on the diagram.
- Assuming fewer roads means shorter
- Add the weights; a zig-zag route through short roads often wins.
- Stopping at the first complete route
- It is only the best so far. Check the rest (pruning makes this quick).
- Answering with a route when a distance is asked for
- Give what is asked: the route, the total, or both, with units.
- Mixing up shortest path and minimum spanning tree
- A spanning tree connects everything; a shortest path joins two vertices.
- Adding times and distances together
- Convert to one quantity first.
Present your search as a table with columns "route" and "total", including pruned routes marked "already over". Circle the minimum and state it with units. If the question involves a required stop, a closure or a new road, write the modified network (or the split into two searches) before you start. Draw the network yourself if it is only given as a table.
Finding a shortest path is like planning the quickest way to a friend's house. You list the different ways you could go, add up the distance of each, and pick the smallest. The trick is to be organised so you do not forget a way, and to give up on any way as soon as it is already longer than the best one you have found. Sometimes the best way zig-zags through side streets rather than following the most obvious road.
Practice questions
Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.
foundation2 marksA network has edges S-A 2, S-B 4, A-B 1, A-T 7 and B-T 3 (km). List the routes from S to T that do not repeat a vertex, and find the shortest path.
Show worked solution →
Routes and lengths: S-A-T ; S-B-T ; S-A-B-T ; S-B-A-T . (1 mark)
The shortest path is S-A-B-T, 6 km. (1 mark) The cheap link A-B makes the longer-looking route the shortest.
foundation1 markWhich of these problems is a shortest path problem? A. Laying cable to connect every house in a street at least cost. B. Finding the quickest drive from home to the airport. C. Visiting every tourist site exactly once. D. Sweeping every street exactly once.
Show worked solution →
B. A shortest path joins two specified vertices (home and the airport) with least total weight. A is a minimum spanning tree, C is a Hamiltonian problem and D is an Eulerian problem.
foundation2 marksTravel times (minutes) are P-Q 6, P-R 9, Q-R 2, Q-S 8, R-S 5, R-T 11, S-T 3. Find the quickest route from P to T.
Show worked solution →
Candidate routes: P-Q-R-S-T ; P-Q-S-T ; P-R-S-T ; P-Q-R-T ; P-R-T . (1 mark)
Quickest: P-Q-R-S-T, 16 minutes. (1 mark)
core3 marksRoads (km): A-B 14, A-C 30, A-F 28, B-C 11, B-D 19, C-D 9, D-E 13, D-F 16, E-F 21. (a) Find the shortest route from A to E and its length. (b) Explain why the two-road route A-F-E is not the shortest.
Show worked solution →
(a) Sensible routes: A-B-D-E ; A-B-C-D-E ; A-F-E ; A-C-D-E ; A-F-D-E . Shortest: A-B-D-E, 46 km. (2 marks)
(b) Fewer roads does not mean a shorter distance; A-F-E totals 49 km, 3 km more than A-B-D-E, because both of its roads are long. (1 mark)
core2 marksUsing the road network in the previous question, find the shortest route from A to E that must pass through C.
Show worked solution →
Split at C: shortest A to C is A-B-C (shorter than the direct road A-C, 30). Shortest C to E is C-D-E . (1 mark)
Total km, via A-B-C-D-E. (1 mark)
core2 marksRoads (km): H-A 7, H-B 4, A-B 2, A-C 5, B-C 8, B-D 6, C-D 1, C-E 3, D-E 4. Find the shortest distance from H to E and state how many different shortest routes there are.
Show worked solution →
Routes of length 14: H-B-D-E (), H-B-A-C-E () and H-B-D-C-E (). No route is shorter (for example H-A-C-E is 15 and H-B-C-E is 15). (1 mark)
The shortest distance is 14 km, achieved by three different routes. (1 mark)
exam4 marksIn the road network A-B 14, A-C 30, A-F 28, B-C 11, B-D 19, C-D 9, D-E 13, D-F 16, E-F 21 (km), the council will build a direct road from A to E that is 4 km shorter than the current shortest road route. (a) Find the length of the new road. (b) After it is built, road B-D is closed for repairs. What is now the shortest route from B to E?
Show worked solution →
(a) The current shortest route from A to E is A-B-D-E, 46 km (checked against A-B-C-D-E 47, A-F-E 49, A-C-D-E 52 and longer routes). (2 marks) The new road is km. (1 mark)
(b) Without B-D, routes from B to E: B-C-D-E ; B-A-E (new road) ; B-C-D-F-E ; B-A-F-E . Shortest: B-C-D-E, 33 km. (1 mark)
exam3 marksA delivery driver can travel from depot D to customer C by the freeway (D-X 40 km at 100 km/h, then X-C 12 km at 60 km/h) or through town (D-Y 18 km at 50 km/h, Y-Z 10 km at 40 km/h, Z-C 8 km at 60 km/h). (a) Which route is shorter in distance? (b) Which is quicker? (c) Explain why the answers differ.
Show worked solution →
(a) Freeway: km. Town: km. The town route is shorter. (1 mark)
(b) Times (time distance speed): freeway h minutes; town h minutes. The freeway is quicker. (1 mark)
(c) The weights depend on what is being minimised. With distances as weights the town route wins; with times as weights the faster freeway wins despite being longer. Always use the weights that match the question. (1 mark)