6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ef029462-ffed-4cdf-87bc-56c8a13d671f-6_609_1283_260_392}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 4 shows a network of roads through eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc is the length of that road in km .
- Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
(5)
There is a fair in village C and you cannot drive through the village. A shortest route from A to H which avoids C needs to be found. - State this new minimal route and its length.
(2)