7 [Answer this question on the insert provided.]
The network below represents a simplified map of the centre of a small town. The arcs represent roads and the weights on the arcs represent distances, in units of 100 metres.
\includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-06_725_1259_495_443}

1. 1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest route from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. State the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(J\), and give their lengths. [7]
   2. The shortest route from \(E\) to \(J\) that passes through every vertex can be treated as being made up of two parts, one from \(E\) to \(A\) and the other from \(A\) to \(J\). Use your answers to part (i) to write down the length of the shortest such route. List the vertices in the order that they are visited in travelling from \(E\) to \(J\) using this route.
   3. Explain why a similar approach to that used in parts (a)(i) and (a)(ii) would not give the shortest route between \(G\) and \(H\) that passes through every vertex.
2. By considering pairings of odd nodes, find the length of the shortest route that starts at \(A\) and ends at \(E\) and uses every arc at least once. \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
   4736
   Decision Mathematics 1
   INSERT for Questions 4 and 7
   Wednesday