1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1e2c1dc4-3724-4bba-961c-1c2ae7e649c4-2_698_1173_447_443}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
[The total weight of the network is 189]
Figure 1 represents a network of pipes in a building. The number on each arc is the length, in metres, of the corresponding pipe.
- Use Dijkstra's algorithm to find the shortest path from A to F . State the path and its length.
On a particular day, Gabriel needs to check each pipe. A route of minimum length, which traverses each pipe at least once and which starts and finishes at A, needs to be found.
- Use an appropriate algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
- State the minimum length of Gabriel's route.
A new pipe, BG, is added to the network. A route of minimum length that traverses each pipe, including BG, needs to be found. The route must start and finish at A.
Gabriel works out that the addition of the new pipe increases the length of the route by twice the length of BG .
- Calculate the length of BG. You must show your working.