A2 June 2019 Q3

EdexcelCurrent spec14 marksShortest Path Travelling Salesman

Figure 2: network on A, B, C, D and E with arcs AB 15, AC 7, AD 18, AE 3 (one-way from A to E), CB 5 (one-way from C to B), CD 4, CE 9, DE 3 — Figure 2

The network in Figure 2 shows the direct roads linking five villages, A, B, C, D and E. The number on each arc represents the length, in miles, of the corresponding road. The roads from A to E and from C to B are one-way, as indicated by the arrows.

(a) Complete the initial distance and route tables for the network provided in the answer book. (2)

Initial distance table (answer book)

	A	B	C	D	E
A
B
C
D
E

Initial route table (answer book)

	A	B	C	D	E
A
B
C
D
E

(b) Perform the first three iterations of Floyd’s algorithm. You should show the distance table and the route table after each of the three iterations. (5)

After five iterations of Floyd’s algorithm the final distance table and partially completed final route table are shown below.

Distance table

	A	B	C	D	E
A	–	12	7	6	3
B	15	–	22	21	18
C	7	5	–	4	7
D	11	9	4	–	3
E	14	12	7	3	–

Route table

	A	B	C	D	E
A	A
B	A	B
C	A	B	C
D	C	C	C	D
E	D	D	D	D	E

(c)

(i) Explain how the partially completed final route table can be used to find the shortest route from E to A.

(ii) State this route. (3)

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)

Mark scheme (c)

Scheme	Marks	AO
(i) Start at E(5^th row) and read across to the A (1^st column), there is a D there so the route from E to A is via D	B1	2.4
Now consider both E to D and D to A – for E reading across to the D (4^th column), there is a D indicating that the shortest path from E to D is ED. For D reading across to the A (1^st column), there is a C indicating that the shortest path from D to A is via C	dB1	2.4
(ii) EDCA	B1	2.2a
	(3)

Notes

(c) B1: Row E column A is D so the route is E to A via D (or implies that the order of the nodes in the route is EDA) or D implied from general argument or Row E column A is D therefore the route begins ED (in all cases must clearly imply row E and column A)

dB1: Row D column A is C therefore the route goes via C (before A) or complete general argument that allows the route from D to A to be found or allow those who say that row D column A is C so the route is EDC and then row C column A is A

B1: CAO (EDCA)

Mark scheme (d)

Scheme	Marks	AO
(i) NNA: D – E – C – B – A – D	B1	1.1b
(ii) 3 + 7 + 5 + 15 + 6 = 36 miles	B1	1.1b
(iii) D – E – D – C – B – A – E – D	B1	3.2a
(iv) e.g. the cycle A – E – D – C – B – A has a length of 30 miles \(\lt\) 36 miles so Mabintou’s route is not optimal	B1	2.4
	(4)
	(14 marks)

Notes

(d)(i) B1: CAO (D – E – C – B – A – D)

(ii) B1: CAO (36 – no units required)

(iii) B1: CAO (D – E – D – C – B – A – E – D) or mentions that the cycle would visit E twice and D three times (or visit D before the end of the cycle – if D visited once stated and it is not clear that this isn’t the start or finish then B0) or mention of E to C via D and A to D via E

(iv) B1: A correct cycle stated (e.g. a cyclic permutation of A – E – D – C – B – A) with corresponding correct length – dependent on second B mark in this part (so must have had 36 in (d)(ii))