3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{162f9d72-84a4-4b1a-93cf-b7eeb7f957ae-04_666_940_173_534}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
The network in Figure 2 shows the direct roads linking five villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E .
The number on each arc represents the length, in miles, of the corresponding road.
The roads from A to E and from C to B are one-way, as indicated by the arrows.
- Complete the initial distance and route tables for the network provided in the answer book.
(2) - Perform the first three iterations of Floyd's algorithm. You should show the distance table and the route table after each of the three iterations.
After five iterations of Floyd's algorithm the final distance table and partially completed final route table are shown below.
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Distance table}
| \cline { 2 - 6 }
\multicolumn{1}{c|}{} | A | B | C | D | E |
| A | - | 12 | 7 | 6 | 3 |
| B | 15 | - | 22 | 21 | 18 |
| C | 7 | 5 | - | 4 | 7 |
| D | 11 | 9 | 4 | - | 3 |
| E | 14 | 12 | 7 | 3 | - |
\captionsetup{labelformat=empty}
\caption{Route table}
| \cline { 2 - 6 }
\multicolumn{1}{c|}{} | A | B | C | D | E |
| A | A | | | | |
| B | A | B | | | |
| C | A | B | C | | |
| D | C | C | C | D | |
| E | D | D | D | D | E |
- Explain how the partially completed final route table can be used to find the shortest route from E to A.
- State this route.
Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table.
- State the cycle obtained using the nearest neighbour algorithm.
- State the length of this cycle.
- Interpret the cycle in terms of the actual villages visited.
- Prove that Mabintou's cycle is not optimal.