5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{48e785c0-7de5-450f-862c-4dd4d169adf9-06_952_1511_230_278}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
[The total weight of the network is 253]
Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road.
One day, Mabintou wishes to travel from A to H. She wishes to minimise the distance she travels.
- Use Dijkstra's algorithm to find the shortest path from A to H . State your path and its length.
On another day, Mabintou wishes to travel from F to K via A.
- Find a route of minimum length from F to K via A and state its length.
The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.
- By considering the pairings of all relevant nodes, find the length of James' route. State the arcs that will need to be traversed twice. You must make your method and working clear.
(6) - State the number of times that James will pass through F.
It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.
- State the vertex where the new inspection route will finish.
- Calculate the difference between the lengths of the two inspection routes.