Route inspection starting and ending at same vertex

4 The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. The total length of the paths shown is 4200 metres. \includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-4_681_1157_450_459}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest distance (in metres) from \(A\) to each of the other vertices. Alex wants to hunt for the treasure. His current location is marked on the network as \(A\). The clues to the location of the treasure are located on the paths. Every path has at least one clue and some paths have more than one. This means that Alex will need to search along the full length of every path to find all the clues.
2. Showing your working, find the length of the shortest route that Alex can take, starting and ending at \(A\), to find every clue. The clues tell Alex that the treasure is located at the point marked as \(H\) on the network.
3. Write down the shortest route from \(A\) to \(H\). Zac also starts at \(A\) and searches along every path to find the clues. He also uses a shortest route to do this, but without returning to \(A\). Instead he proceeds directly to the treasure at \(H\).
4. Calculate the length of the shortest route that Zac can take to search for all the clues and reach the treasure.

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.

1. Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\). You must show clearly:
   1. the order in which you labelled the vertices,
   2. how you found a route of minimum length from your labelling. Each night a security guard walks along each of the paths in Figure 2 at least once.
2. The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
   (4 marks)

6 A graph is shown in Fig. 1.1.
The graph is weighted to form the network represented by the weighted matrix in Fig. 1.2. The weights represent distances in km.
A dash (-) means that there is no direct arc between that pair of vertices. \begin{figure}[h] \end{figure} \begin{table}[h] \end{table} The shortest path from D to F has total weight 6.

1. Write down a path from D to F of total weight 6. The total weight of the 12 arcs in the network is 56.
2. Use the route inspection algorithm to calculate the total weight of the least weight route that covers every arc at least once, starting at vertex A.
3. Determine the total weight of the least weight route that covers every arc at least once, starting at vertex B but finishing at any vertex. Sasha wants to find a continuous route through every vertex, starting and finishing at vertex A, with the least total weight.
4. 1. Use an appropriate algorithm to find a lower bound for the total weight of Sasha's route.
   2. Use the Nearest Neighbour Algorithm, starting at vertex A, to find an upper bound for the total weight of Sasha's route. Sasha decides to use the route \(A - B - F - E - C - D - A\).
5. Comment on the suitability of this route as a solution to Sasha's problem.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 167]
Figure 3 represents a network of paths. The number on each arc gives the time, in minutes, to travel along that path.

1. Use Dijkstra's algorithm to find the quickest route from A to H. State your quickest route and the time taken.
   (5) Kevin must walk along each path at least once and return to his starting point.
2. Use an appropriate algorithm to find the time of Kevin's quickest possible route, starting and finishing at A. You should make your method and working clear.

3. \begin{figure}[h] \end{figure} Figure 3 shows a network of roads. The number on each arc represents the length, in km, of that road.

1. Use Dijkstra's algorithm to find the shortest route from A to I. State your shortest route and its length.
   (5) Sam has been asked to inspect the network and assess the condition of the roads. He must travel along each road at least once, starting and finishing at A .
2. Use an appropriate algorithm to determine the length of the shortest route Sam can travel. State a shortest route.
   (4)
   (The total weight of the network is 197 km )

5 Answer part (i) of this question on the insert provided. Rhoda Raygh enjoys driving but gets extremely irritated by speed cameras.
The network represents a simplified map on which the arcs represent roads and the weights on the arcs represent the numbers of speed cameras on the roads. The sum of the weights on the arcs is 72 . \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-05_874_1484_664_333}

1. Rhoda lives at Ayton ( \(A\) ) and works at Kayton ( \(K\) ). Use Dijkstra's algorithm on the diagram in the insert to find the route from \(A\) to \(K\) that involves the least number of speed cameras and state the number of speed cameras on this route.
2. In her job Rhoda has to drive along each of the roads represented on the network to check for overhanging trees. This requires finding a route that covers every arc at least once, starting and ending at Kayton (K). Showing all your working, find a suitable route for Rhoda that involves the least number of speed cameras and state the number of speed cameras on this route.
3. If Rhoda checks the roads for overhanging trees on her way home, she will instead need a route that covers every arc at least once, starting at Kayton and ending at Ayton. Calculate the least number of speed cameras on such a route, explaining your reasoning.