4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-5_889_1591_258_239}
\captionsetup{labelformat=empty}
\caption{Figure 3
[0pt]
[The total weight of the network is 100]}
\end{figure}
Figure 3 represents a network of pipes in a building. The number on each arc represents the length, in metres, of the corresponding pipe.
- Use Dijkstra's algorithm to find the shortest path from A to J . State your path and its length.
On a particular day Kim needs to check each pipe. A route of minimum length, which traverses each pipe at least once and starts and finishes at A, needs to be found.
- Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
- Write down a possible route, giving its length.
All the pipes directly attached to B are removed. Kim needs to check all the remaining pipes and may now start at any vertex and finish at any vertex. A route is required that excludes all those pipes directly attached to B .
- State all possible combinations of starting and finishing points so that the length of Kim's route is minimised. State the length of Kim's route.