A2 June 2025 Q3

EdexcelCurrent spec10 marksShortest Path Travelling Salesman

Figure 1: network on villages A to G with arcs AG 11, GF 12, GE 24 (one-way from G to E), GC 47, AE 35, AB 9 (one-way from A to B), AD 25 (one-way from A to D), BF 35, BD 8, BC 40, CD 17, FE 14, FD 31, ED 11 — Figure 1

Direct roads between seven villages, A, B, C, D, E, F and G, are represented in Figure 1. The weight on each arc is the time, in minutes, taken to travel along the corresponding road. Three roads, AB, AD and GE, are one-way, as indicated by the arrow on the corresponding arc.

Floyd’s algorithm is to be used to find the complete network of shortest times between the seven villages.

(a) Set up an initial time matrix for this network. (2)

The time matrix after three iterations of Floyd’s algorithm is shown below.

	A	B	C	D	E	F	G
A	–	9	49	17	35	44	11
B	∞	–	40	8	∞	35	87
C	∞	40	–	17	∞	75	47
D	∞	8	17	–	11	31	64
E	35	44	84	11	–	14	46
F	∞	35	75	31	14	–	12
G	11	20	47	28	24	12	–

(b) Perform the next two iterations of Floyd’s algorithm that follow from the table above.
You should show only the time matrix after each iteration. (5)

The final time matrix after completion of Floyd’s algorithm is shown below.

	A	B	C	D	E	F	G
A	–	9	34	17	28	23	11
B	54	–	25	8	19	33	45
C	58	25	–	17	28	42	47
D	46	8	17	–	11	25	37
E	35	19	28	11	–	14	26
F	23	32	42	25	14	–	12
G	11	20	45	28	24	12	–

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)

Mark scheme (a)

Scheme

Marks

	A	B	C	D	E	F	G
A	-	9	∞	25	35	∞	11
B	∞	-	40	8	∞	35	∞
C	∞	40	-	17	∞	∞	47
D	∞	8	17	-	11	31	∞
E	35	∞	∞	11	-	14	∞
F	∞	35	∞	31	14	-	12
G	11	∞	47	∞	24	12	-

B2, 1, 0

1.1b
1.1b

(2)

Notes

a1B1: At least three rows and three columns correct (condone at most 2 empty cells but accept consistent blanks for the leading diagonal)

a2B1: CAO

Mark scheme (c)

Scheme	Marks	AO
(i) NNA starting at B: B – D – E – F – G – A – C – B	B1	2.2a
(ii) Time taken: 8 + 11 + 14 + 12 + 11 + 34 + 25 = 115 (minutes)	B1	1.1b
(iii) Actual villages visited: BDEFGA\(\underline{\text{BD}}\)C\(\underline{\text{D}}\)B	B1	2.2a
	(3)
	(10 marks)

Notes

ci1B1: CAO (Nearest neighbour cycle starting at B – must include return to B) (condone the use of arcs BD DE EF FG GA AC CB – must be written in this manner and not AG or BC)

cii2B1: Correct time

ciii3B1: Correct route – must be stated as nodes