3.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{162f9d72-84a4-4b1a-93cf-b7eeb7f957ae-04_666_940_173_534}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\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.
\begin{enumerate}[label=(\alph*)]
\item Complete the initial distance and route tables for the network provided in the answer book.\\
(2)
\item 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]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Distance table}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & A & B & C & D & E \\
\hline
A & - & 12 & 7 & 6 & 3 \\
\hline
B & 15 & - & 22 & 21 & 18 \\
\hline
C & 7 & 5 & - & 4 & 7 \\
\hline
D & 11 & 9 & 4 & - & 3 \\
\hline
E & 14 & 12 & 7 & 3 & - \\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Route table}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & A & B & C & D & E \\
\hline
A & A &  &  &  &  \\
\hline
B & A & B &  &  &  \\
\hline
C & A & B & C &  &  \\
\hline
D & C & C & C & D &  \\
\hline
E & D & D & D & D & E \\
\hline
\end{tabular}
\end{center}
\end{table}
\item \begin{enumerate}[label=(\roman*)]
\item Explain how the partially completed final route table can be used to find the shortest route from E to A.
\item 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.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item State the cycle obtained using the nearest neighbour algorithm.
\item State the length of this cycle.
\item Interpret the cycle in terms of the actual villages visited.
\item Prove that Mabintou's cycle is not optimal.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 2019 Q3 [14]}}