Network in Graph Theory
How to Find the shortest route in a network
Use this to find the lowest-weight route between two points on a weighted network.
Before you start
- Be able to read a weighted network: vertices (points) joined by edges with numbers.
- Add several numbers together accurately.
- Understand that a route is a sequence of connected edges from start to end.
When to use it
Use this to find the lowest-weight route between two points on a weighted network.
The steps
- Label every edge with its weight (distance, time or cost).
- List the sensible routes between the start and end vertices.
- Total the weights along each route.
- Compare the totals and choose the smallest.
- Show the totals for each route so the comparison is clear.
Worked example
A network joins towns A, B, C and D. The roads and their distances are A–B = 5 km, A–C = 3 km, B–C = 1 km, B–D = 4 km and C–D = 6 km.
Find the shortest route from A to D.
- Label every edge with its weight: A–B = 5 km, A–C = 3 km, B–C = 1 km, B–D = 4 km, C–D = 6 km.
- List the sensible routes from A to D: A–B–D, A–C–D, A–C–B–D and A–B–C–D.
- Total the weights along each route: A–B–D = 5 + 4 = 9 km; A–C–D = 3 + 6 = 9 km; A–C–B–D = 3 + 1 + 4 = 8 km; A–B–C–D = 5 + 1 + 6 = 12 km.
- Compare the totals 9, 9, 8 and 12 km, and choose the smallest, which is 8 km.
- Show the totals so the comparison is clear: route A–C–B–D at 8 km is shorter than every other route.
A second example, with a twist
This network has five towns and the weights are travel costs in ringgit, so there are more routes to total, and the route through the fewest towns is not the cheapest. A network joins towns P, Q, R, S and T.
The travel costs are P–Q = RM8, P–R = RM5, Q–S = RM4, R–S = RM3, Q–T = RM9, S–T = RM6 and R–T = RM15. Find the cheapest route from P to T.
- Label every edge with its cost: P–Q = RM8, P–R = RM5, Q–S = RM4, R–S = RM3, Q–T = RM9, S–T = RM6, R–T = RM15.
- List the sensible routes from P to T: P–Q–T, P–Q–S–T, P–R–T, P–R–S–T and P–R–S–Q–T.
- Total the costs along each route: P–Q–T = 8 + 9 = RM17; P–Q–S–T = 8 + 4 + 6 = RM18; P–R–T = 5 + 15 = RM20; P–R–S–T = 5 + 3 + 6 = RM14; P–R–S–Q–T = 5 + 3 + 4 + 9 = RM21.
- Compare the totals RM17, RM18, RM20, RM14 and RM21, and choose the smallest, which is RM14.
- Show the totals so the comparison is clear: P–R–S–T at RM14 is cheapest, even though P–R–T uses fewer roads.
Formula pages
Practise this in a KBAT problem
Frequently asked questions
Do I have to list every possible route?
List every sensible route from start to finish. You can leave out routes that clearly loop back on themselves or take an obvious long detour, but include any path that could reasonably be short.
Missing a route is risky, because the shortest one is sometimes the path you did not expect to check.
Is the route through the fewest towns always the shortest?
No. A route with fewer edges can still have larger weights and end up longer overall.
A path that passes through more towns but along short, cheap edges may total less. That is why you must add up the weights of each route and compare the totals, not just count how many stops there are.
What should I do if two routes have the same total?
Then both routes are shortest and either one is a correct answer. It is good practice to state that they tie and give the equal total, for example 'A–C–D and A–B–D both measure 9 km'.
Showing every total in your working makes it clear why more than one route can win.