4 P72094A 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. A B C D E F A – 12 32 24 29 11 B 12 – 17 8 ∞ ∞ C 32 17 – 4 12 ∞ D 24 ∞ 4 – ∞ 13 E ∞ ∞ 12 18 – 12 F 11 ∞ ∞ 13 12 – 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) 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 ∞ ∞ 12 18 – 12 F 11 23 40 13 12 – 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) 5 Turn over P72094A 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. (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) (Total for Question 3 is 10 marks)