D1.3.1 Algorithm for finding the shortest route around a network,…

Section
D1.3 Algorithms on graphs II
Level
AS & A level
Statement
Algorithm for finding the shortest route around a network, travelling along every edge at least once and ending at the start vertex (The Route Inspection Algorithm).
Guidance
Also known as the ‘Chinese postman’ problem. Students will be expected to use inspection to consider all possible pairings of odd nodes. The network will contain at most four odd nodes. If the network has more than four odd nodes then additional information will be provided that will restrict the number of pairings that will need to be considered.
Since 2018
24 parts, 81 marks · topic pages: Route inspection and the travelling salesman problem, Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd)

Back to the checklist

June 2025 · AS Paper 2 (Decision 1) · Q3(c) 5 marks
Ruby manages road maintenance from her office located at junction B. She needs to walk along each road at least once, starting and finishing at her office. Road AE is temporarily blocked so she is unable to walk along it. Ruby wishes to minimise her journey time. (c) (i) Use an appropriate algorithm to find the roads that Ruby needs to traverse twice. You must make your method and working clear. (ii) Calculate Ruby’s journey time. (5)
June 2025 · AS Paper 2 (Decision 1) · Q3(d) 2 marks
Ruby can save some time by choosing to start her route from any junction and to finish at her home at A. Road AE is still blocked and Ruby again wishes to minimise her journey time. (d) (i) Write down the junction at which Ruby should start. (ii) Calculate how much time she would save. (2)
June 2025 · Paper 3D (Decision 1) · Q4(b) 5 marks
On Monday afternoon, Turvi needs a route that traverses each corridor at least once. She plans to start at J and finish at A and wants to minimise the distance travelled. (b) (i) By considering the pairings of all relevant nodes, find the corridors that would need to be traversed twice. You must make your method and working clear. (ii) State the total length of this route. (5)
June 2025 · Paper 3D (Decision 1) · Q4(c) 2 marks
Turvi discovers that she cannot walk along corridors AB, CD and JK because they are being decorated. Turvi walks from J to A travelling along all the other corridors at least once. She does this in the minimum distance possible. (c) Determine the difference between the length of the route Turvi travels and the length of the route found in (b). You must make the values used in your calculation clear. (2)
June 2024 · AS Paper 2 (Decision 1) · Q3(c) 1 mark
The warehouse manager wants to check that all of the walkways are in good condition. Their inspection route starts at B and finishes at C. The inspection route must traverse each walkway at least once and be as short as possible. (c) State the arcs that are traversed twice. (1)
June 2024 · AS Paper 2 (Decision 1) · Q3(d) 1 mark
(d) State the number of times that H appears in the inspection route. (1)
June 2024 · AS Paper 2 (Decision 1) · Q3(e) 2 marks
The warehouse manager finds that the total length of the inspection route is 172 metres. (e) Determine the value of x and the value of y (2)
June 2024 · Paper 3D (Decision 1) · Q3(b) 6 marks
Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track. (b) By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must • state which tracks she will repeat in her route • state the total length of her route (6)
June 2024 · Paper 3D (Decision 1) · Q3(c) 2 marks
The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route. (c) Determine which route, Abi’s or Tarig’s, is shorter. You must make your working clear. (2)
June 2023 · AS Paper 2 (Decision 1) · Q5(c) 6 marks
Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road. You are given that x > 1.6 A route is required that • starts and finishes at the same vertex • traverses each road at least once • minimises the total time taken The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes. Given that the inspection route contains two roads that need to be traversed twice, (c) determine the range of possible values of x, making your reasoning clear. (6)
June 2023 · Paper 3D (Decision 1) · Q5(a) 5 marks
5. A B H C G F E J Figure 5 [The total weight of the network is 423] Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. A B C E F G H J A – B – C – – E – F – G – H – J – Table of shortest distances A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J. (a) (i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice. (ii) State the total length of this route. (5)
June 2022 · AS Paper 2 (Decision 1) · Q3(d) 6 marks
An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G. Daisy plans to cycle along every track in the new network, starting and finishing at H. Given that the addition of either track CD or track EG will not affect the final values obtained in (c), (d) use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must • state which tracks Daisy will repeat in her route • state the total length of her route (6)
June 2022 · Paper 3D (Decision 1) · Q2(b) 2 marks
The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E. (b) (i) State the edges that will need to be traversed twice. (ii) Find the length of Blanche’s route. (2)
June 2022 · Paper 3D (Decision 1) · Q2(c) 5 marks
It is now decided to start the inspection route at A and finish at K. Blanche must minimise the length of her route and travel along each track at least once. (c) By considering the pairings of all relevant nodes, find the length of Blanche’s new route. You must make your method and working clear. (5)
Nov 2021 · Paper 3D (Decision 1) · Q4(c) 4 marks
The final time matrix after completion of Floyd’s algorithm is shown below. A B C E F A – B – C – – E – F – A route is needed that minimises the total time taken to traverse each road at least once. The route must start at B and finish at E. (c) Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear. (4)
Nov 2021 · Paper 3D (Decision 1) · Q4(d) 1 mark
(d) Write down the length of the route. (1)
Oct 2020 · AS Paper 2 (Decision 1) · Q3(c) 6 marks
A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex. Given that the time taken to traverse this route is 318 minutes, (c) use an appropriate algorithm to determine the value of x, showing your working clearly. (6)
Oct 2020 · Paper 3D (Decision 1) · Q6(b) 9 marks
The weights on the arcs in Figure 4 represent distances. The weight on arc EF is x where 12 < x < 26 and the weight on arc DG is y where 0 < y < 10 An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at A and has a length of 409 It is also given that the length of the shortest route from F to G via A is 140 (b) Using appropriate algorithms, find the value of x and the value of y. (9)
June 2019 · AS Paper 2 (Decision 1) · Q4(b) 1 mark
An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length. (b) State the arcs that are traversed twice. (1)
June 2019 · AS Paper 2 (Decision 1) · Q4(c) 1 mark
(c) State the number of times that vertex C appears in the inspection route. (1)
June 2019 · AS Paper 2 (Decision 1) · Q4(d) 1 mark
(d) Determine the length of the inspection route. (1)
June 2019 · Paper 3D (Decision 1) · Q2(b) 4 marks
On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G. (b) Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear. (4)
June 2019 · Paper 3D (Decision 1) · Q2(c) 1 mark
(c) Find the length of Naasir’s route. (1)
June 2019 · Paper 3D (Decision 1) · Q2(d) 3 marks
On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B. (d) (i) Determine the possible starting and finishing points so that the length of Naasir’s route is minimised. You must give reasons for your answer. (ii) Find the length of Naasir’s new route. (3)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.