A LevelFurther MathsEdexcelDecision 1Exam QuestionsAlgorithms on GraphsThe Travelling Salesman Problem

The Travelling Salesman Problem (Edexcel A Level Further Maths: Decision 1): Exam Questions

Exam code: 9FM0

47 mins4 questions

2 marks

Explain clearly the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

How did you do?

3 marks

Write your answer in the Answer Booklet (opens in a new tab).

	A	B	C	D	E	F	G
A	–	17	24	16	21	18	41
B	17	–	35	25	30	31	$x$
C	24	35	–	28	20	35	32
D	16	25	28	–	29	19	45
E	21	30	20	29	–	22	35
F	18	31	35	19	22	–	37
G	41	$x$	32	45	35	37	–

The table shows the least distances, in km, by road between seven towns, A, B, C, D, E, F and G. The least distance between B and G is $x$ km, where $x$ > 25

Preety needs to visit each town at least once, starting and finishing at A. She wishes to minimise the total distance she travels.

Starting by deleting B and all of its arcs, find a lower bound for Preety’s route.

How did you do?

4 marks

Write your answer in the Answer Booklet (opens in a new tab).

Pretty found the nearest neighbour routes from each of A and C. Given that the sum of the lengths of these routes is 331 km,

find $x$ , making your method clear.

How did you do?

2 marks

Write down the smallest interval that you can be confident contains the optimal length of Preety’s route. Give your answer as an inequality.

How did you do?

Was this exam question helpful?

2 marks

The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one‑way only.

	A	B	C	D	E	F
A	–	12	32	24	29	11
B	12	–	17	8	$\infty$	$\infty$
C	32	17	–	4	12	$\infty$
D	24	$\infty$	4	–	$\infty$	13
E	$\infty$	$\infty$	12	18	–	12
F	11	$\infty$	$\infty$	13	12	–

Table 1

By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 below.

A graph diagram with points A-F; lines connect B-D, C-D, B-C, C-E, E-F. Line weights: B-C 17, B-D 8, C-D 4, C-F 18, C-E 12, D-F 13, E-F 12.

How did you do?

4 marks

Floyd’s algorithm is to be used to find the complete network of shortest distances between the six classrooms.

The distance matrix after two iterations of Floyd’s algorithm is shown in Table 2.

	A	B	C	D	E	F
A	–	12	29	20	29	11
B	12	–	17	8	41	23
C	29	17	–	4	12	40
D	24	36	4	–	53	13
E	$\infty$	$\infty$	12	18	–	12
F	11	23	40	13	12	–

Table 2

Perform the next two iterations of Floyd's algorithm that follow from Table 2. You should show the distance matrix after each iteration.

Two grid tables labelled "3rd iteration" and "4th iteration" compare letters A to F, with some cells marked with a dash.

How did you do?

4 marks

The final distance matrix after completion of Floyd’s algorithm is shown in Table 3.

	A	B	C	D	E	F
A	–	12	24	20	23	11
B	12	–	12	8	24	21
C	28	17	–	4	12	17
D	24	21	4	–	16	13
E	23	29	12	16	–	12
F	11	23	17	13	12	–

Table 3

Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.

(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.

How did you do?

Was this exam question helpful?

5 marks

A network graph with nodes A-J connected by weighted edges, showing values like 34, 42, 50. Total weight is 423. Nodes are labelled with letters.

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	D	E	F	G	H	J
A	–	34	51	31	79	20	8	55	61
B	34	–	17	65	45	54	42	21	27
C	51	17	–	82	28	71	59	22	10
D	31	65	82	–	87	22	23	86	92
E	79	45	28	87	–	65	87	30	18
F	20	54	71	22	65	–	28	75	81
G	8	42	59	23	87	28	–	63	69
H	55	21	22	86	30	75	63	–	12
J	61	27	10	92	18	81	69	12	–

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.

(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.

How did you do?

3 marks

Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.

How did you do?

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.

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.

How did you do?

2 marks

By deleting G and all of its arcs, find a lower bound for the length of Pete’s route.

Pete decides to take the route he found in (c).

How did you do?

1 mark

Interpret the route in terms of the actual towns visited.

How did you do?

Was this exam question helpful?

3 marks

The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

	A	B	C	D	E	F	G	H	J
A	–	50	59	26	50	40	87	63	59
B	50	–	28	61	79	63	45	64	48
C	59	28	–	33	57	35	70	36	45
D	26	61	33	–	24	64	71	37	33
E	50	79	57	24	–	40	64	30	31
F	40	63	35	64	40	–	47	70	71
G	87	45	70	71	64	47	–	34	67
H	63	64	36	37	30	70	34	–	33
J	59	48	45	33	31	71	67	33	–

Use Prim's algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.

How did you do?

1 mark

State the weight of the minimum spanning tree found in part (a).

How did you do?

1 mark

Draw the minimum spanning tree using the vertices given in Diagram 1 below.

Circular diagram with ten labelled points: A to J, placed equidistantly. Points are marked by dots, each labelled with a letter. Titled 'Diagram 1'.

How did you do?

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.

Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route.

How did you do?

3 marks

(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.

How did you do?

1 mark

Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles was found.

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.

How did you do?

2 marks

By deleting A and all of its arcs, find a lower bound for the length of the historian’s route.

How did you do?

1 mark

By deleting J and all of its arcs, a lower bound of length 274 miles was found.

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.

How did you do?

Was this exam question helpful?

More Revision Notes you might like

	A	B	C	D	E	F	G
A	–	17	24	16	21	18	41
B	17	–	35	25	30	31	$x$
C	24	35	–	28	20	35	32
D	16	25	28	–	29	19	45
E	21	30	20	29	–	22	35
F	18	31	35	19	22	–	37
G	41	$x$	32	45	35	37	–

	A	B	C	D	E	F
A	–	12	24	20	23	11
B	12	–	12	8	24	21
C	28	17	–	4	12	17
D	24	21	4	–	16	13
E	23	29	12	16	–	12
F	11	23	17	13	12	–

	A	B	C	D	E	F	G	H	J
A	–	34	51	31	79	20	8	55	61
B	34	–	17	65	45	54	42	21	27
C	51	17	–	82	28	71	59	22	10
D	31	65	82	–	87	22	23	86	92
E	79	45	28	87	–	65	87	30	18
F	20	54	71	22	65	–	28	75	81
G	8	42	59	23	87	28	–	63	69
H	55	21	22	86	30	75	63	–	12
J	61	27	10	92	18	81	69	12	–

	A	B	C	D	E	F	G	H	J
A	–	50	59	26	50	40	87	63	59
B	50	–	28	61	79	63	45	64	48
C	59	28	–	33	57	35	70	36	45
D	26	61	33	–	24	64	71	37	33
E	50	79	57	24	–	40	64	30	31
F	40	63	35	64	40	–	47	70	71
G	87	45	70	71	64	47	–	34	67
H	63	64	36	37	30	70	34	–	33
J	59	48	45	33	31	71	67	33	–

	A	B	C	D	E	F	G
A	–	17	24	16	21	18	41
B	17	–	35	25	30	31	$x$
C	24	35	–	28	20	35	32
D	16	25	28	–	29	19	45
E	21	30	20	29	–	22	35
F	18	31	35	19	22	–	37
G	41	$x$	32	45	35	37	–

	A	B	C	D	E	F
A	–	12	24	20	23	11
B	12	–	12	8	24	21
C	28	17	–	4	12	17
D	24	21	4	–	16	13
E	23	29	12	16	–	12
F	11	23	17	13	12	–

	A	B	C	D	E	F	G	H	J
A	–	34	51	31	79	20	8	55	61
B	34	–	17	65	45	54	42	21	27
C	51	17	–	82	28	71	59	22	10
D	31	65	82	–	87	22	23	86	92
E	79	45	28	87	–	65	87	30	18
F	20	54	71	22	65	–	28	75	81
G	8	42	59	23	87	28	–	63	69
H	55	21	22	86	30	75	63	–	12
J	61	27	10	92	18	81	69	12	–

	A	B	C	D	E	F	G	H	J
A	–	50	59	26	50	40	87	63	59
B	50	–	28	61	79	63	45	64	48
C	59	28	–	33	57	35	70	36	45
D	26	61	33	–	24	64	71	37	33
E	50	79	57	24	–	40	64	30	31
F	40	63	35	64	40	–	47	70	71
G	87	45	70	71	64	47	–	34	67
H	63	64	36	37	30	70	34	–	33
J	59	48	45	33	31	71	67	33	–

	A	B	C	D	E	F	G
A	–	17	24	16	21	18	41
B	17	–	35	25	30	31	$x$
C	24	35	–	28	20	35	32
D	16	25	28	–	29	19	45
E	21	30	20	29	–	22	35
F	18	31	35	19	22	–	37
G	41	$x$	32	45	35	37	–

	A	B	C	D	E	F
A	–	12	24	20	23	11
B	12	–	12	8	24	21
C	28	17	–	4	12	17
D	24	21	4	–	16	13
E	23	29	12	16	–	12
F	11	23	17	13	12	–

	A	B	C	D	E	F	G	H	J
A	–	34	51	31	79	20	8	55	61
B	34	–	17	65	45	54	42	21	27
C	51	17	–	82	28	71	59	22	10
D	31	65	82	–	87	22	23	86	92
E	79	45	28	87	–	65	87	30	18
F	20	54	71	22	65	–	28	75	81
G	8	42	59	23	87	28	–	63	69
H	55	21	22	86	30	75	63	–	12
J	61	27	10	92	18	81	69	12	–

	A	B	C	D	E	F	G	H	J
A	–	50	59	26	50	40	87	63	59
B	50	–	28	61	79	63	45	64	48
C	59	28	–	33	57	35	70	36	45
D	26	61	33	–	24	64	71	37	33
E	50	79	57	24	–	40	64	30	31
F	40	63	35	64	40	–	47	70	71
G	87	45	70	71	64	47	–	34	67
H	63	64	36	37	30	70	34	–	33
J	59	48	45	33	31	71	67	33	–