2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{162f9d72-84a4-4b1a-93cf-b7eeb7f957ae-03_663_1421_203_322}
\captionsetup{labelformat=empty}
\caption{Figure 1
[0pt]
[The total weight of the network is 370]}
\end{figure}
Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.
- Use Dijkstra's algorithm to find the shortest path from A to D, stating the path and its length.
On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G .
- Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
- Find the length of Naasir's route.
On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B .
- Determine the possible starting and finishing points so that the length of Naasir's route is minimised. You must give reasons for your answer.
- Find the length of Naasir's new route.