6 The network below shows the lengths of roads, in miles, connecting 10 towns, \(A , B , \ldots , J\).
- Use Dijkstra's algorithm on the network to find the shortest distance from \(A\) to \(J\). Show all your working at each vertex.
- Write down the corresponding route.
- A new road is to be constructed connecting \(B\) to \(G\). Find the length of this new road if the shortest distance from \(A\) to \(J\) is reduced by 10 miles. State the new route.
(3 marks)
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-12_1846_1719_861_150}