A2 October 2020 Q3

EdexcelCurrent spec9 marksShortest PathTravelling Salesman

3.

Figure 2: network on A, B, C, D and E with arcs AB 8, AC 4, AD 7, BC 3, BE 10, CE 6, DE 1 and DC 1 (one-way from D to C)
Figure 2

Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is 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 five villages.

(a) Set up initial time and route matrices. (2)

The matrices after two iterations of Floyd’s algorithm are shown below.

Time matrix

ABCDE
A–84718
B8–31510
C43–116
D7151–1
E181061–

Route matrix

ABCDE
AABCDB
BABCAE
CABCAE
DAACDE
EBBCDE
(b) Perform the next two iterations of Floyd’s algorithm that follow from the tables above. You should show the time and route matrices after each iteration. (4)

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

Final time matrix

ABCDE
A–7478
B7–3109
C43–76
D541–1
E6521–
(c)
(i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times.
(ii) Find the time taken for this cycle.
(iii) Interpret the cycle in terms of the actual villages visited. (3)
‹ Previous15 of 41 in Shortest PathNext ›