A2 June 2022 Q3

EdexcelCurrent spec10 marksShortest PathTravelling Salesman

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

ABCDEF
A–1232242911
B12–178∞∞
C3217–412∞
D24∞4–∞13
E∞∞1218–12
F11∞∞1312–

Table 1

(a) By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. (2)
Diagram 1: vertices A to F with arcs BC 17, BD 8 (one-way from B to D), CD 4, CE 12, ED 18 (one-way from E to D), EF 12, DF 13; vertex A has no arcs
Diagram 1

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.

ABCDEF
A–1229202911
B12–1784123
C2917–41240
D24364–5313
E∞∞1218–12
F1123401312–

Table 2

(b) Perform the next two iterations of Floyd’s algorithm that follow from Table 2. You should show the distance matrix after each iteration. (4)

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

ABCDEF
A–1224202311
B12–1282421
C2817–41217
D24214–1613
E23291216–12
F1123171312–

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)
‹ Previous9 of 41 in Shortest PathNext ›