D1.3.2 The practical and classical Travelling Salesman problems. The…

Section
D1.3 Algorithms on graphs II
Level
A level only
Statement
The practical and classical Travelling Salesman problems. The classical problem for complete graphs satisfying the triangle inequality. Determination of upper and lower bounds using minimum spanning tree methods. The nearest neighbour algorithm.
Guidance
The use of short cuts to improve upper bound is included. The conversion of a network into a complete network of shortest ‘distances’ is included.
Since 2018
14 parts, 31 marks · topic pages: Route inspection and the travelling salesman problem

Back to the checklist

June 2025 · Paper 3D (Decision 1) · Q3(c) 3 marks
The final time matrix after completion of Floyd’s algorithm is shown below. A B C E F G A – B – C – – E – F – G – Albert must visit each village. He will start and finish at B and wishes to minimise the total time taken to visit each village. (c) (i) Use the nearest neighbour algorithm, starting at B, to find a Hamiltonian cycle in the complete network of shortest times shown above. (ii) Find the total travel time for this cycle. (iii) Given that he travels the Hamiltonian cycle found in (c)(i), interpret this cycle in terms of the actual villages visited by Albert. (3)
June 2024 · Paper 3D (Decision 1) · Q2(d) 1 mark
A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled. (d) Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route. (1)
June 2024 · Paper 3D (Decision 1) · Q2(e) 3 marks
(e) (i) Use the nearest neighbour algorithm, starting at D, to find an upper bound for the length of the historian’s route. (ii) Write down the route which gives this upper bound. (3)
June 2024 · Paper 3D (Decision 1) · Q2(f) 1 mark
Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles was found. (f) State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer. (1)
June 2024 · Paper 3D (Decision 1) · Q2(g) 2 marks
(g) By deleting A and all of its arcs, find a lower bound for the length of the historian’s route. (2)
June 2024 · Paper 3D (Decision 1) · Q2(h) 1 mark
By deleting J and all of its arcs, a lower bound of length 274 miles was found. (h) State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer. (1)
June 2023 · Paper 3D (Decision 1) · Q5(c) 2 marks
Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels. (c) Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound. (2)
June 2023 · Paper 3D (Decision 1) · Q5(d) 2 marks
(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)
June 2023 · Paper 3D (Decision 1) · Q5(e) 1 mark
Pete decides to take the route he found in (c). (e) Interpret the route in terms of the actual towns visited. (1)
June 2022 · Paper 3D (Decision 1) · Q3(c) 4 marks
The final distance matrix after completion of Floyd’s algorithm is shown in Table 3. A B C E F A – B – C – – E – F – Table 3 Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled. (c) (i) Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances. (ii) Find the length of each of the two cycles. (iii) State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka’s route. (4)
Nov 2021 · Paper 3D (Decision 1) · Q3(c) 2 marks
A B C E F G H J Table 2 Table 2 shows the distances, in miles, between town J and towns A, B, C, D, E, F, G and H. Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels. (c) Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav’s route. You must state your route and its length. (2)
Nov 2021 · Paper 3D (Decision 1) · Q3(d) 2 marks
(d) Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route. (2)
Oct 2020 · Paper 3D (Decision 1) · Q3(c) 3 marks
The final time matrix after completion of Floyd’s algorithm is shown below. Final time matrix A B C E A – B – C – – E – (c) (i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times. (ii) Find the time taken for this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (3)
June 2019 · Paper 3D (Decision 1) · Q3(d) 4 marks
Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table. (d) (i) State the cycle obtained using the nearest neighbour algorithm. (ii) State the length of this cycle. (iii) Interpret the cycle in terms of the actual villages visited. (iv) Prove that Mabintou’s cycle is not optimal. (4)

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.