Combined Dijkstra and route inspection

5 The network below represents the streets in a small village. The weights on the arcs show distances in metres. The total length of all the streets shown is 2200 metres. \includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-07_499_1264_367_402}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(H\).
2. Write down the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(G\). Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at \(A\).
3. Explain why Sheng-Li will need to repeat some streets.
4. Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at \(A\), to deliver leaflets to every street. The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from \(A\), with Sheng-Li delivering to one side of \(A B\) and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice. Nadia and Sheng-Li travel \(A - B - C - E\). At this point Sheng-Li is called back to \(A\). He travels along \(E - C - A\), delivering leaflets on one side of \(C A\). Nadia completes the leaflet delivery on her own.
5. Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.
   [0pt] [4]

4. \begin{figure}[h] \end{figure} Figure 3 represents a network of pipes in a building. The number on each arc represents the length, in metres, of the corresponding pipe.

1. Use Dijkstra's algorithm to find the shortest path from A to J . State your path and its length. On a particular day Kim needs to check each pipe. A route of minimum length, which traverses each pipe at least once and starts and finishes at A, needs to be found.
2. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Write down a possible route, giving its length. All the pipes directly attached to B are removed. Kim needs to check all the remaining pipes and may now start at any vertex and finish at any vertex. A route is required that excludes all those pipes directly attached to B .
4. State all possible combinations of starting and finishing points so that the length of Kim's route is minimised. State the length of Kim's route.

6. \begin{figure}[h] \end{figure} [The total weight of the network is 269] Figure 3 models a network of roads. The number on each edge gives the time taken, in minutes, to travel along the corresponding road.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. Alan needs to travel along all the roads to check that they are in good repair. He wishes to complete his route as quickly as possible and will start at his home, H, and finish at his workplace, D.
2. By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in Alan's inspection route from H to D. You must make your method and working clear. For Alan's inspection route from H to D
3. 1. state the number of times vertex C will appear,
   2. state the number of times vertex D will appear.
4. Determine whether it would be quicker for Alan to start and finish his inspection route at H , instead of starting at H and finishing at D . You must explain your reasoning and show all your working.

6. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 223]} Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.

1. Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length. On a particular day, Pamela must include C in her route.
2. Find the shortest route from A to B that includes C , and state its length.
   (2) Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A .
3. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, and calculate its length. You must make your calculation clear. Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
5. State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).

4. \begin{figure}[h] \end{figure} [The total weight of the network is 275]
Figure 5 models a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each edge gives the time, in minutes, to travel along the corresponding road. Mandeep wishes to travel from A to J as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. On Monday, Mandeep must travel from D to H via A.
2. Find the shortest time needed to travel from D to H via A . State the quickest route. On Wednesday, Mandeep needs to travel along each road to check that it is in good repair. She wishes to minimise the total time required to traverse the network. Mandeep plans to start and finish her inspection route at G.
3. Use an appropriate algorithm to find the roads that need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, giving its duration. On Friday, all the roads leading directly to B are closed. Mandeep needs to check all the remaining roads and may start at any village and finish at any village. A route is required that excludes all those roads leading directly to B .
5. State all possible combinations of starting and finishing points so that the duration of Mandeep's route is minimised. Calculate the duration of Mandeep's minimum route.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 423]
Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. \begin{table}[h] \end{table} A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J .

1. 1. By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.
   2. State the total length of this route.
2. Starting at A, use Prim's algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.
3. Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete's route. Write down the route that gives this upper bound.
4. By deleting G and all of its arcs, find a lower bound for the length of Pete's route. Pete decides to take the route he found in (c).
5. Interpret the route in terms of the actual towns visited.

5 Answer this question on the insert provided. The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres. The sum of the weights on the arcs is 765 metres. \includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}

1. Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.
2. In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors. The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.
3. On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?

7 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows the times, in seconds, taken by Craig to walk along walkways connecting ten hotels in Las Vegas. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-07_1435_1267_525_351} The total of all the times in the diagram is 2280 seconds.

1. 1. Craig is staying at the Circus ( \(C\) ) and has to visit the Oriental ( \(O\) ). Use Dijkstra's algorithm on Figure 2 to find the minimum time to walk from \(C\) to \(O\).
   2. Write down the corresponding route.
2. 1. Find, by inspection, the shortest time to walk from \(A\) to \(M\).
   2. Craig intends to walk along all the walkways. Find the minimum time for Craig to walk along every walkway and return to his starting point.

4 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows 11 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-04_1762_1056_516_484} The total of all of the times is 308 minutes.

1. 1. Use Dijkstra's algorithm on Figure 2 to find the minimum time to travel from \(A\) to \(K\).
   2. State the corresponding route.
2. Find the length of an optimum Chinese postman route around the network, starting and finishing at \(A\). (The minimum time to travel from \(D\) to \(H\) is 40 minutes.)

The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.

1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
2. 1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
   2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]

\includegraphics{figure_4}