To find the shortest route, list every route from the start to the end, add the weights, and choose the smallest total. In a small network, this listing is the whole method.
This lesson follows distinguishing directed, weighted and simple graphs in the SPM Mathematics networks chapter.
How do you list routes without missing one?
Start at the beginning and follow one branch to the end. Then go back to the last choice and try the next branch.
Never use the same vertex twice in one route. Each finished route is written as a string of letters.
Worked example: five stops
Stops A to E are joined by roads with distances in km: AB 4, AC 2, BC 1, BD 5, CD 8, CE 10 and DE 2. Find the shortest route from A to E.
| Route | Working | Total (km) |
|---|---|---|
| A C E | 2 + 10 | 12 |
| A C D E | 2 + 8 + 2 | 12 |
| A C B D E | 2 + 1 + 5 + 2 | 10 |
| A B D E | 4 + 5 + 2 | 11 |
| A B C E | 4 + 1 + 10 | 15 |
| A B C D E | 4 + 1 + 8 + 2 | 15 |
| A B D C E | 4 + 5 + 8 + 10 | 27 |
The shortest route is A C B D E, with a total of 10 km.
The mistake that costs marks
The common slip is to choose the route with the fewest stops. A C E has only two roads, but it is 12 km. The route A C B D E has four roads and is shorter.
| Wrong | Right | |
|---|---|---|
| Choice | A C E | A C B D E |
| Reason | Fewest roads | Smallest total distance |
| Total | 12 km | 10 km |
Another slip is to stop after the first route you find. Write every route before you compare.
Check yourself
Vertices P, Q, R and S have edges PQ 3, PR 7, QR 2, QS 6 and RS 3. Find the shortest route from P to S.
Answer
P Q S: 3 + 6 = 9.
P R S: 7 + 3 = 10.
P Q R S: 3 + 2 + 3 = 8.
P R Q S: 7 + 2 + 6 = 15.
The shortest route is P Q R S, with a total of 8.
What to study next
Test all four lessons in the networks practice set. The algebra step-repair trainer gives you practice at checking each line of arithmetic, which every route total needs. Log slips in the mistake log and paper-error review.
If you want a teacher to check your route lists, see online one-to-one Mathematics tuition.