3. \begin{figure}[h] \end{figure} 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.

1. Set up initial time and route matrices. The matrices after two iterations of Floyd's algorithm are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	8	4	7	18
   B	8	-	3	15	10
   C	4	3	-	11	6
   D	7	15	1	-	1
   E	18	10	6	1	-

   \end{table} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Route matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	A	B	C	D	B
   B	A	B	C	A	E
   C	A	B	C	A	E
   D	A	A	C	D	E
   E	B	B	C	D	E

   \end{table}
2. 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. The final time matrix after completion of Floyd's algorithm is shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Final time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	7	4	7	8
   B	7	-	3	10	9
   C	4	3	-	7	6
   D	5	4	1	-	1
   E	6	5	2	1	-

   \end{table}
3. 1. Use the nearest neighbour algorithm, starting at A , to find a Hamiltonian cycle in the complete network of shortest times.
   2. Find the time taken for this cycle.
   3. Interpret the cycle in terms of the actual villages visited.