6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-08_1031_1502_242_333}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
\section*{[The total weight of the network is 223]}
Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.
- Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length.
On a particular day, Pamela must include C in her route.
- Find the shortest route from A to B that includes C , and state its length.
(2)
Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A . - 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, and calculate its length. You must make your calculation clear.
Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
- State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).