Shortest paths and Dijkstra's algorithm for VCE General Mathematics Unit 4 Networks and decision mathematics
“Determine the shortest path between two specified vertices in a graph, digraph or network by inspection, and use Dijkstra's algorithm to find the shortest path between a given vertex and each of the other vertices”
A shortest path is the route of least total weight between two vertices. For small networks, list and total the candidate routes. Dijkstra's algorithm gives the start label 0, updates each neighbour's tentative label to the smaller of its current value and (permanent label edge weight), makes the smallest tentative label permanent, and repeats; the permanent labels are the shortest distances from the start to every vertex, and tracing back gives the routes.
Jump to a section
What this dot point is asking
A shortest path problem asks for the route of least total weight between two vertices of a weighted graph: the shortest distance between two towns, the quickest time through a set of streets, or the cheapest sequence of flights. VCAA wants you to recognise this problem type, solve small cases by inspection, and use Dijkstra's algorithm to solve larger ones, including networks with one-way (directed) edges and questions that ask for the shortest path from one vertex to each of the other vertices.
Shortest path questions appear in almost every Networks and decision mathematics section. Examination 1 typically shows a network and asks for a shortest distance as a multiple-choice option; Examination 2 asks for the distance, the route, or the effect of changing the network (a road closure, a required stop), and the examiners regularly remind students to give the distance when asked for a distance, not just the route.
The answer
Recognising the problem
The shortest path problem is one of several "which route?" problems in the module, and choosing the wrong model is a common way to lose marks.
| The question wants | Problem type | Tool |
|---|---|---|
| The least total weight from one vertex to another | Shortest path | Inspection or Dijkstra's algorithm |
| The least total weight of edges that connects every vertex | Minimum spanning tree | Inspection or Prim's algorithm |
| A route that uses every edge exactly once | Eulerian trail or circuit | Degree conditions |
| A route that visits every vertex exactly once | Hamiltonian path or cycle | Inspection |
| The greatest amount that can flow from source to sink | Maximum flow | Minimum cut |
A shortest path visits only the vertices it needs; it does not have to pass through every vertex, and the edges it uses do not form a tree covering the whole network.
Shortest path by inspection
For a small network, list every sensible route from the start to the finish, add the weights along each one, and choose the smallest. Two cautions:
- More edges can be shorter. A route that zig-zags through extra vertices may have a smaller total than a direct-looking route. In the network below the direct-looking routes S-A-C-T (15) and S-B-D-T (15) both lose to the five-edge route S-B-A-C-D-T (13).
- Inspection is error-prone on bigger networks. Once there are more than about five or six vertices, the number of routes grows quickly and it is easy to miss one. That is exactly why an algorithm is useful.
Dijkstra's algorithm
Dijkstra's algorithm builds shortest paths outward from the start, one vertex at a time, and never has to go back and fix a vertex once it is finished. Each vertex carries a label: the length of the shortest route to it found so far.
- Give the start vertex the label 0 and make it permanent. All other vertices have no label yet (think of it as infinity).
- For the vertex just made permanent, look at each of its neighbours that is not yet permanent. Calculate (permanent label edge weight). If this is smaller than the neighbour's current tentative label (or the neighbour has no label), replace the label and note which vertex it came from.
- Of all the vertices with tentative labels, choose the one with the smallest label and make it permanent.
- Repeat steps 2 and 3 until the destination is permanent (or, if asked for shortest paths to every vertex, until all vertices are permanent).
- Trace back from the destination through the "came from" vertices to read off the route.
In Dijkstra's algorithm a permanent label is the length of the shortest path from the start to that vertex, and it never changes. At each step, make permanent the vertex with the smallest tentative label, then update its neighbours by keeping the smaller of their current label and (new permanent label edge weight). The algorithm needs non-negative edge weights and respects edge directions in a digraph.
Why does it work? When a vertex has the smallest tentative label, no other route can reach it more cheaply, because any other route would have to pass through a vertex whose label is already at least as large, and edge weights cannot be negative. So its label can safely be fixed.
Dijkstra's algorithm step by step
Here is the algorithm on this network, from S to T. Each row shows the vertex made permanent and the tentative labels after its neighbours are updated. A label that improves is marked with the vertex it now comes from.
| Step | Made permanent | A | B | C | D | T |
|---|---|---|---|---|---|---|
| 1 | S (0) | 4 (S) | 2 (S) | |||
| 2 | B (2) | 3 (B) | 10 (B) | 12 (B) | ||
| 3 | A (3) | 8 (A) | 12 (B) | |||
| 4 | C (8) | 10 (C) | 14 (C) | |||
| 5 | D (10) | 13 (D) | ||||
| 6 | T (13) |
The key moments:
- Step 2. B is permanent with label 2. A currently has label 4 (straight from S), but through B it can be reached with . Since , A's label improves to 3. This is the step that inspection usually misses.
- Step 3. A is permanent with label 3. C had label 10 (via B), but through A it is , so it improves.
- Step 4. C is permanent with label 8. D improves from 12 to , and T gets a first label of .
- Step 5. D is permanent with label 10. T improves from 14 to .
Tracing back: T came from D, D from C, C from A, A from B, B from S. The shortest path is S-B-A-C-D-T with length 13. The permanent labels also give the shortest distance from S to every other vertex: A 3, B 2, C 8, D 10.
Directed networks
In a digraph (one-way streets, one-way flights, a pipe that only flows one way) Dijkstra's algorithm works in exactly the same way, except that from each permanent vertex you may only follow edges that point away from it. Two consequences:
- The shortest path from to may be a different length from the shortest path from to .
- Some vertices may not be reachable at all. If no edge points into a vertex, nothing can reach it; its label stays empty.
Common question variations
- Shortest path to every vertex. Keep going until every vertex is permanent. The permanent labels are the answers.
- A road is closed or a new road opens. The old answer may no longer be valid. Re-run the algorithm on the changed network, or at least re-check every route that used the changed edge. A new road only helps if it creates a route shorter than the current shortest.
- The route must pass through a particular vertex. Split the trip: shortest path from start to the required vertex, plus shortest path from the required vertex to the finish.
- Multiple shortest paths. Two routes can tie. If asked "how many different shortest paths", check for ties when tracing back.
- Shortest path in a table (adjacency matrix with weights). Read each row as the edges out of that vertex and run the algorithm on the table in the same way.
Inspection on a small network
Find the shortest path from A to D in the network A-B 5, A-C 2, C-B 2, B-D 4, C-D 7 (km).
List the routes. A-B-D: . A-C-D: . A-C-B-D: . A-B-C-D: .
Choose the smallest. A-C-B-D, 8 km.
Marker's note: when asked for the shortest distance, the answer is the number 8 km. Writing only the route gives away the mark; the 2023 examiners' report drew attention to exactly this.
Dijkstra's algorithm with a table
Roads join a home H to a school K: H-P 3, H-Q 7, P-Q 3, P-R 8, Q-R 2, Q-S 6, R-S 2, R-K 4, S-K 1 (km). Find the shortest path from H to K.
Run the algorithm.
| Step | Made permanent | Updated tentative labels |
|---|---|---|
| 1 | H (0) | P 3 (H), Q 7 (H) |
| 2 | P (3) | Q 6 (P), R 11 (P) |
| 3 | Q (6) | R 8 (Q), S 12 (Q) |
| 4 | R (8) | S 10 (R), K 12 (R) |
| 5 | S (10) | K 11 (S) |
| 6 | K (11) |
Trace back. K from S, S from R, R from Q, Q from P, P from H: H-P-Q-R-S-K, 11 km.
Marker's note: the direct-looking route H-Q-R-K is km. The algorithm finds that going the "long way" through P and S saves 2 km.
A one-way network
One-way streets (minutes): P to Q 3, P to R 7, Q to R 2, Q to S 6, R to S 3, S to Q 1, R to T 9, S to T 4, T to R 2. Find the quickest route from P to T.
Run the algorithm, following arrows only. P 0. Update Q 3, R 7. Make Q permanent (3): R improves to , S becomes 9. Make R permanent (5): S improves to , T becomes . Make S permanent (8): T improves to (the edge S to Q cannot help because Q is already permanent). Make T permanent (12).
Answer. P-Q-R-S-T, 12 minutes. From T you can only leave along T to R, so the quickest trip back from T to S is minutes, and P cannot be reached at all.
Marker's note: in a digraph, reverse journeys are separate questions. Never assume the return trip has the same length.
A road closure and a required stop
In the H to K network, the road Q-R is closed. Find the new shortest distance. Then, with Q-R open again, find the shortest distance from H to K that calls at R.
Closure. Without Q-R: H 0; P 3, Q 7; P (3): Q 6, R 11; Q (6): S 12; R (11): K 15 (S stays 12 because ); S (12): K 13; K (13). New shortest distance 13 km via H-P-Q-S-K, an increase of 2 km.
Required stop. Shortest H to R is 8 (from the original run). Shortest R to K is . Total km.
Marker's note: for a required stop, add two separate shortest paths. For a closure, re-run: the new shortest path can use completely different roads.
Shortest path or minimum spanning tree?
Both use a weighted graph and both involve "cheapest", so students confuse them. The difference is the goal.
- A shortest path connects two vertices and minimises the length of that one route.
- A minimum spanning tree connects all the vertices and minimises the total length of all the edges used.
In the six-vertex network above, the minimum spanning tree uses edges A-B (1), S-B (2), C-D (2), D-T (3) and A-C (5), total 13, and it happens to contain the shortest path from S to T. That is a coincidence of this network. In general the MST route between two vertices can be much longer than the shortest path, because the MST is optimised for total cable, not for any one journey.
- Making permanent a vertex that is not the smallest
- At every step you must make permanent the tentative label that is smallest overall, not simply the next vertex along the edge you just used.
- Overwriting a smaller label with a bigger one
- Only replace a tentative label if the new value is smaller.
- Updating a permanent vertex
- Once a vertex is permanent its label is final; ignore edges back into it.
- Ignoring arrows in a digraph
- Travel only in the direction of the arrow.
- Giving the route when the distance was asked for (or the reverse)
- Read the command word and give what is asked, with units.
- Confusing shortest path with minimum spanning tree
- A shortest path joins two vertices; a spanning tree joins all of them.
- Assuming fewer edges means shorter
- Always add the weights.
In Examination 2, show Dijkstra's algorithm as a table (steps down the side, vertices across the top), crossing out labels as they improve, or write the labels in boxes beside each vertex on the diagram. Finish with the route, written as a list of vertices, and the total with units. In Examination 1, where only the answer counts, a quick inspection of the three or four most plausible routes is usually faster than the full algorithm, but check any route that uses a small "shortcut" edge between two otherwise longer routes.
Imagine you want the quickest way to walk to school through a maze of streets. Instead of trying every possible route, you work outwards from home. First you find the nearest corner, and you know for sure that is the quickest way to get there. Then you look at how far the next corners are through that one, keep the best distance you have found for each, and lock in the next nearest. You keep going, always locking in whichever unlocked corner is closest, until you lock in the school. The locked-in number at the school is the shortest distance, and following the trail back tells you which way to walk.
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 weighted graph has edges A-B 5, A-C 2, C-B 2, B-D 4 and C-D 7 (distances in km). By listing the routes, find the shortest path from A to D and its length.
Show worked solution →
List the routes from A to D that do not repeat a vertex and total each one:
- A-B-D:
- A-C-D:
- A-C-B-D:
- A-B-C-D:
The shortest path is A-C-B-D, length 8 km. (1 mark for the route, 1 mark for the length.) Notice it uses more edges than the two 9 km routes: fewer edges does not mean shorter.
foundation2 marksDuring Dijkstra's algorithm from vertex S, vertex Q has a tentative label of 11. The vertex just made permanent is P with label 6, and the edge P-Q has weight 4. (a) What happens to Q's label? (b) What would happen if P-Q had weight 7?
Show worked solution →
(a) The route through P reaches Q with length , which is less than the current label 11, so Q's tentative label is updated to 10 (and P is recorded as the vertex it came from). (1 mark)
(b) Through P the length would be , which is more than 11, so the label stays at 11. A label is only ever replaced by a smaller one. (1 mark)
foundation1 markWhich one of the following is found by Dijkstra's algorithm? A. The minimum total length of edges needed to connect every vertex. B. The shortest path from one vertex to each of the other vertices. C. A route that uses every edge exactly once. D. The maximum flow from a source to a sink.
Show worked solution →
B. Dijkstra's algorithm finds shortest paths from a single starting vertex. Option A is a minimum spanning tree (Prim's algorithm), option C is an Eulerian trail, and option D is the maximum-flow minimum-cut problem.
core3 marksRoads (lengths in km) join a home H to a school K: H-P 3, H-Q 7, P-Q 3, P-R 8, Q-R 2, Q-S 6, R-S 2, R-K 4, S-K 1. Use Dijkstra's algorithm to find the shortest path from H to K and its length, showing the order in which vertices are made permanent.
Show worked solution →
Start: H is permanent with label 0.
| Step | Made permanent | Tentative labels after updating |
|---|---|---|
| 1 | H (0) | P 3, Q 7 |
| 2 | P (3) | Q 6 (via P), R 11 |
| 3 | Q (6) | R 8 (via Q), S 12 |
| 4 | R (8) | S 10 (via R), K 12 |
| 5 | S (10) | K 11 (via S) |
| 6 | K (11) |
(2 marks for the correct labels and order.)
Trace back from K: K came from S, S from R, R from Q, Q from P, P from H. The shortest path is H-P-Q-R-S-K, length 11 km. (1 mark)
core2 marksFor the road network in the previous question, write down the length of the shortest path from H to each of P, Q, R and S.
Show worked solution →
Dijkstra's algorithm gives these directly as the permanent labels: P 3 km, Q 6 km, R 8 km, S 10 km. (2 marks, 1 for any two correct.)
This is the "shortest path between a given vertex and each of the other vertices" that the study design describes: one run of the algorithm answers all of them.
core3 marksA one-way street network has directed edges (times in minutes) P to Q 3, P to R 7, Q to R 2, Q to S 6, R to S 3, S to Q 1, R to T 9, S to T 4, T to R 2. (a) Find the shortest time from P to T and the route. (b) Is it possible to travel from T to P? (c) Find the shortest time from T to S.
Show worked solution →
(a) Dijkstra from P, following arrow directions only: P 0; Q 3, R 7; make Q permanent (3), update R to 5 and S to 9; make R permanent (5), update S to 8 and T to 14; make S permanent (8), update T to 12; T permanent (12). Route P-Q-R-S-T, 12 minutes. (1 mark)
(b) No. There is no edge pointing into P, so P cannot be reached from anywhere. (1 mark)
(c) From T the only exit is T to R (2), then R to S (3): 5 minutes. (1 mark)
exam3 marksIn the road network H-P 3, H-Q 7, P-Q 3, P-R 8, Q-R 2, Q-S 6, R-S 2, R-K 4, S-K 1 (km), the road Q-R is closed for repairs. (a) Find the new shortest distance from H to K and a route that achieves it. (b) By how much has the shortest distance increased?
Show worked solution →
(a) Re-run the algorithm without Q-R. H 0; P 3, Q 7; P permanent (3): Q 6, R 11; Q permanent (6): S 12; R permanent (11): S stays 12 (since ), K 15; S permanent (12): K 13; K permanent (13).
The shortest distance is 13 km, via H-P-Q-S-K (). (2 marks)
(b) The original shortest distance was 11 km, so it has increased by 2 km. (1 mark)
Always re-run from scratch (or at least re-check every route through the closed road). Simply deleting the closed road from the old path does not give a valid route.
exam2 marksIn the original road network (with Q-R open), a student must travel from H to K but must call at R on the way. Find the minimum distance.
Show worked solution →
Split the journey at the required vertex: shortest H to R, plus shortest R to K.
- Shortest H to R: from the algorithm, 8 km (H-P-Q-R).
- Shortest R to K: R-K is 4, R-S-K is , so 3 km.
Minimum distance: , so 11 km. (1 mark for splitting, 1 for the total.) Here the required stop happens to lie on the unrestricted shortest path already, so the answer is unchanged; if it did not, the total would be longer.