Dijkstra combined with Chinese Postman

4 The diagram opposite shows a network of roads on a housing estate. The number on each edge is the length, in metres, of the road. Joe is starting a kitchen-fitting business.

1. Joe delivers leaflets advertising his business. He walks along all of the roads at least once, starting and finishing at \(C\). Find the length of an optimal Chinese postman route for Joe.
2. Joe gets a job fitting a kitchen in a house at \(T\). Joe starts from \(C\) and wishes to drive to \(T\). Use Dijkstra's algorithm on the diagram opposite to find the minimum distance to drive from \(C\) to \(T\). State the corresponding route. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-08_1791_1705_916_155}
   (b) \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-09_2395_1602_312_260}

5 The network on the page opposite shows the times, in minutes, taken by police cars to drive along roads connecting 12 places, \(A , B , \ldots , L\). On a particular day, there are three police cars in the area at \(A , E\) and \(J\). There is an emergency at \(G\) and all three police cars drive to \(G\).

1. 1. Use Dijkstra's algorithm on the network, starting from \(\boldsymbol { G }\), to find the minimum driving time for each of the police cars to arrive at \(G\).
   2. For each of the police cars, write down the route corresponding to the minimum driving time in your answer to part (a)(i).
2. Each day, a police car has to drive along each road at least once, starting and finishing at \(A\). For an optimal Chinese postman route:
   1. find the driving time for the police car;
   2. state the number of times that the vertex \(B\) would appear.
      \includegraphics[max width=\textwidth, alt={}]{77c4efd4-a905-48f3-a6f7-36b0e47dbc6d-13_2486_1709_221_153}

1 In the network below, the arcs represent the roads in Ayton, the vertices represent roundabouts, and the arc weights show the number of traffic lights on each road. Sam is an evening class student at Ayton Academy ( \(A\) ). She wants to drive from the academy to her home ( \(H\) ). Sam hates waiting at traffic lights so she wants to find the route for which the number of traffic lights is a minimum. \includegraphics[max width=\textwidth, alt={}, center]{bb7fb141-ef42-42af-b052-d8e20d6e5157-02_786_1097_482_523}

1. Apply Dijkstra's algorithm to find the route that Sam should use to travel from \(A\) to \(H\). At each vertex, show the temporary labels, the permanent label and the order of permanent labelling. In the daytime, Sam works for the highways department. After an electrical storm, the highways department wants to check that all the traffic lights are working. Sam is sent from the depot ( \(D\) ) to drive along every road and return to the depot. Sam needs to pass every traffic light, but wants to repeat as few as possible.
2. Find the minimum number of traffic lights that must be repeated. Show your working. Suppose, instead, that Sam wants to start at the depot, drive along every road and end at her home, passing every traffic light but repeating as few as possible.
3. Find a route on which the minimum number of traffic lights must be repeated. Explain your reasoning.

3 The total weight of the arcs in the network below is 230 . \includegraphics[max width=\textwidth, alt={}, center]{012e87d3-d157-485c-a8bc-2c59c0862f87-3_545_1394_310_331}

1. Apply Dijkstra's algorithm to the copy of the network in the answer book to find the least weight path from \(A\) to \(H\). Give the path and its weight. In the remainder of this question, any least weight paths required may be found without using a formal algorithm.
2. The arc \(A D\) is removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A D\) ) at least once.
3. Suppose, instead, that the arc \(A D\) is available, but \(\operatorname { arcs } A C\) and \(C D\) are both removed. Apply the route inspection algorithm, showing your working, to find the weight of the least weight closed route that uses every arc (except \(A C\) and \(C D\) ) at least once.

4 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-3_918_1242_351_443} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the lengths of roads in kilometres.

1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest path 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. Find the route of the shortest path from \(A\) to \(G\). The total weight of the arcs is 120 kilometres.
2. By using an appropriate algorithm, find the length of a shortest route that uses every road starting and ending at \(A\). You should explain your method.
3. Find the length of a shortest route that uses every road starting at \(A\) and ending at \(G\). You should explain your method.

4 The network below represents a small village. The arcs represent the streets and the weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{7ca6d572-d776-4ad7-a0ed-9ec43c975585-04_503_1179_324_482}

1. Use Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from \(A\) to \(G\). Hannah wants to deliver newsletters along every street; she will start and end at \(A\).
2. Which standard network problem does Hannah need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 3.7 km .
3. Hannah knows that she will need to travel \(A B\) and \(E F\) twice, once in each direction. With this information, use an appropriate algorithm to find the length of the shortest route that Hannah can use. Show all your working. (You may find the lengths of shortest paths between vertices by inspection.) There are street name signs at each vertex except for \(A\) and \(E\). Hannah's friend Peter wants to check that the signs have not been vandalised. He will start and end at \(B\). The table below shows the complete set of shortest distances between vertices \(B , C , D , F\) and \(G\).

   	\(B\)	\(C\)	\(D\)	\(F\)	\(G\)
   \(B\)	-	0.2	0.1	0.3	0.75
   \(C\)	0.2	-	0.3	0.5	0.95
   \(D\)	0.1	0.3	-	0.2	0.65
   \(F\)	0.3	0.5	0.2	-	0.45
   \(G\)	0.75	0.95	0.65	0.45	-

4. Apply the nearest neighbour method to this table, starting from \(B\), to find an upper bound for the distance that Peter must travel.
5. Apply Prim's algorithm to the matrix formed by deleting the row and column for vertex \(G\) from the table. Start building your tree at vertex \(B\). Draw your tree. Give the order in which vertices are built into your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Peter must travel.

6 [Answer part (i) of this question on the insert provided.]
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}

1. Use Dijkstra's algorithm, starting from checkpoint \(\boldsymbol { A }\), to find the least travel time from \(A\) to \(D\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from \(A\) to \(D\).
2. By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at \(A\). You should show your method clearly.
3. Starting from \(A\), apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from \(A\) and finishing at \(D\).

4. \begin{figure}[h] \end{figure} [The total weight of the network is 293] Figure 2 models a network of roads. The number on each edge gives the time, in minutes, taken 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.
   (6) The road represented by edge GJ is closed due to essential maintenance. Sahil needs to travel along all the other roads to check that they are in good repair. Sahil wishes to complete his route as quickly as possible and will start and finish at the same vertex.
2. Use the route inspection algorithm to find the duration of Sahil's quickest route. State the edges that will need to be traversed twice. You should make your method and working clear.
   (6) Given that Sahil will start and finish at vertex C,
3. state the number of times that Sahil will visit vertex E and vertex F in his inspection route.
   (2)

1 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{e1495f6b-c09f-46a1-a6f8-02354e28887a-02_533_1353_342_395}

1. Apply Dijkstra's algorithm to the copy of this network in the insert to find the least weight path from \(A\) to \(F\). State the route of the path and give its weight.
2. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. Write down a closed route that has this least weight. An extra arc is added, joining \(B\) to \(E\), with weight 2 .
3. Write down the new least weight path from \(A\) to \(F\). Explain why the new least weight closed route, that uses every arc at least once, has no repeated arcs.

3 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows roads connecting some places of interest in Berlin. The numbers represent the times taken, in minutes, to walk along the roads. \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-4_1427_1404_502_319} The total of all walking times is 167 minutes.

1. Mia is staying at \(D\) and is to visit \(H\).
   1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(D\) to \(H\).
   2. Write down the corresponding route.
2. Each day, Leon has to deliver leaflets along all of the roads. He must start and finish at \(A\).
   1. Use your answer to part (a) to write down the shortest walking time from \(D\) to \(A\).
   2. Find the walking time of an optimum Chinese Postman route for Leon. (6 marks)

\includegraphics{figure_1} Figure 1 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Oliver wishes to travel by road from A to K as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to K. State the quickest route. \hfill [6]

On a particular day Oliver must travel from B to K via A.

1. Find a route of minimal time from B to K that includes A, and state its length. \hfill [2]

Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.

1. Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear. \hfill [7]

\includegraphics{figure_3} Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.

1. Use Dijkstra's algorithm to find the shortest distance from \(A\) to \(H\). [5]
2. Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at \(A\), and find its length. [The total weight of the network is 1241] [6]

\includegraphics{figure_3}

1. Apply Dijkstra's algorithm to the copy of this network in the answer booklet to find the least weight path from A to F. State the route of the path and give its weight. [6]

In the remainder of this question, any least weight paths required may be found without using a formal algorithm.

1. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. [3]
2. Find the weight of the least weight route that uses every arc at least once, starting at A and ending at F. Explain how you reached your answer. [4]

Answer this question on the insert provided. The vertices in the network below represent the junctions between main roads near Ayton (A). The arcs represent the roads and the weights on the arcs represent distances in miles. \includegraphics{figure_4}

1. On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from A to H. You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from A to H and give its length in miles. [7]

Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.

1. Which standard network problem does Simon need to solve to find the shortest route that uses every arc? [1]

The total weight of all the arcs is 67.5 miles.

1. Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) [5]

Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from A and ending at H.

1. Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? [2]

There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.

1. Show that the nearest neighbour method fails on this network if it is started from A. [1]
2. Apply the nearest neighbour method starting from C to find an upper bound for the distance that Amber must travel. [3]
3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node A and all the arcs that are directly joined to node A. Start building your tree at node B. (You do not need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert. Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel. [6]