4. \begin{figure}[h] \end{figure} Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the six cities.
An initial route matrix is given in the answer book.

1. Set up the initial time matrix.
2. Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration. The final time matrix after completion of Floyd's algorithm is shown below.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	A	B	C	D	E	F
   A	-	57	95	147	63	220
   B	57	-	72	204	120	197
   C	95	72	-	242	158	125
   D	147	204	242	-	84	275
   E	63	120	158	84	-	191
   F	220	197	125	275	191	-

   A route is needed that minimises the total time taken to traverse each road at least once.
   The route must start at B and finish at E .
3. Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
4. Write down the length of the route.