4 Answer parts (i) and (ii) on the insert provided.
Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-5_536_828_573_642}
\captionsetup{labelformat=empty}
\caption{Fig. 4}
\end{figure}
- Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]
- Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector.
A bridge is built giving a direct road between P and Q of length 12 km .
- What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)
- What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)
- Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once.
Give this town and justify your answer.