7.04a Shortest path: Dijkstra's algorithm

6 [Figure 1, printed on a separate sheet, is provided for use in this question.]
A theme park is built on two levels. The levels are connected by a staircase. There are five rides on each of the levels. The diagram shows the ten rides: \(A , B , \ldots \ldots J\). The numbers on the edges represent the times, in minutes, taken to travel between pairs of rides. \includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-05_984_1593_584_226}

1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from \(A\) to \(J\).
2. A new staircase is built connecting rides \(B\) and \(G\). The time taken to travel from \(B\) to \(G\) using this staircase is \(x\) minutes, where \(x\) is an integer. The time taken to travel from \(A\) to \(G\) is reduced, but the time taken to travel from \(A\) to \(J\) is not reduced. Find two inequalities for \(x\) and hence state the value of \(x\).
   (4 marks)

6 The network below shows the lengths of roads, in miles, connecting 10 towns, \(A , B , \ldots , J\).

1. Use Dijkstra's algorithm on the network to find the shortest distance from \(A\) to \(J\). Show all your working at each vertex.
2. Write down the corresponding route.
3. 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}

6 The network opposite shows some roads connecting towns. The number on each edge represents the length, in miles, of the road connecting a pair of towns.

1. 1. Use Dijkstra's algorithm on the network to find the minimum distance from \(A\) to \(J\).
   2. Write down the corresponding route.
2. The road \(A J\) is a dual carriageway. Ken drives at 60 miles per hour on this road and drives at 50 miles per hour on all other roads. Find the minimum time to travel from \(A\) to \(J\).
   \includegraphics[max width=\textwidth, alt={}]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-15_2487_1714_221_152}

7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has eight vertices, \(A , B , \ldots , H\), and edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges \(E H\) and \(G H\) are functions of \(x\) and \(y\). \includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-07_1170_1705_596_164} Given that there are three routes from \(A\) to \(H\) with the same minimum weight, use Dijkstra's algorithm on Figure 2 to find:

1. this minimum weight;
2. the values of \(x\) and \(y\).

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}

4 The network below shows some pathways at a school connecting different departments. The number on each edge represents the time taken, in minutes, to walk along that pathway. Carol, the headteacher, wishes to walk from her office ( \(O\) ) to the Drama department (D) .

1. 1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(O\) to \(D\).
   2. Write down the corresponding route.
2. On another occasion, Carol needs to go from her office to the Business Studies department \(( B )\).
   1. Write down her minimum walking time.
   2. Write down the route corresponding to this minimum time. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-08_1499_1714_1208_153}

4 The edges on the network below represent some major roads in a city. The number on each edge is the minimum time taken, in minutes, to drive along that road.

1. 1. Use Dijkstra's algorithm on the network to find the shortest possible driving time from \(A\) to \(J\).
   2. Write down the corresponding route.
2. A new ring road is to be constructed connecting \(A\) to \(J\) directly. Find the maximum length of this new road from \(A\) to \(J\) if the time taken to drive along it, travelling at an average speed of \(90 \mathrm {~km} / \mathrm { h }\), is to be no more than the time found in part (a)(i). \section*{(a)(i)} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-08_912_1276_1053_429}

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}

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

12 JANUARY 2005
Afternoon
1 hour 30 minutes

• This insert should be used to answer Questions 4 and 7.
• Write your name, centre number and candidate number in the spaces provided at the top of this page.
• Write your answers to Questions 4 and 7 in the spaces provided in this insert, and attach it to your answer booklet.

4

1. 	\(A\)	\(B\)	C	D	\(E\)	\(F\)	G	\(H\)
   A	-	4	2	3	-	-	-	-
   \(B\)	4	-	1	-	3	-	-	-
   C	2	1	-	2	-	6	5	-
   \(D\)	3	-	2	-	-	-	4	-
   E	-	3	-	-	-	8	-	7
   \(F\)	-	-	6	-	8	-	-	8
   \(G\)	-	-	5	4	-	-	-	9
   \(H\)	-	-	-	-	7	8	9	-

2. B \(E\) \(C\) F
   • \(H\) \(A\) •
   • \({ } ^ { \text {F } }\)
   H D
   G
3. \(\_\_\_\_\)
4. \(\_\_\_\_\)
5. \(\_\_\_\_\) 7
   1. 1. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_191_1179_269_482} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_871_1557_612_335} Shortest route from \(A\) to \(E =\) \(\_\_\_\_\) Length = \(\_\_\_\_\) Shortest route from \(A\) to \(J =\) \(\_\_\_\_\) Length = \(\_\_\_\_\)
      2. Length of route \(=\) \(\_\_\_\_\) Vertices visited in order \(\_\_\_\_\)
      3. Explanation \(\_\_\_\_\)
   2. \(\_\_\_\_\) Length = \(\_\_\_\_\)

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.

12 JUNE 2006
Afternoon
1 hour 30 minutes

• This insert should be used to answer Question 6.
• Write your name, centre number and candidate number in the spaces provided at the top of this page.
• Write your answers to Question 6 in the spaces provided in this insert, and attach it to your answer booklet.

6

1. 
   Key: \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_193_949_214_712} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-10_1157_1600_648_303} Route of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) Length of shortest path from \(A\) to \(J =\) \(\_\_\_\_\) metres
2. 1. \(\_\_\_\_\) Shortest distance \(=\) \(\_\_\_\_\) metres
   2. \includegraphics[max width=\textwidth, alt={}, center]{f2b85dfb-49df-4ea5-b118-9b95f0b27bad-11_979_1429_276_440}
      Shortest distance = \(\_\_\_\_\) metres

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.

5 The arcs in the network below represent the tracks in a forest and the weights on the arcs represent distances in km. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_543_1269_392_438} Dijkstra's algorithm is to be used to find the shortest path from \(A\) to \(G\).

1. Apply Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). Show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Do not cross out your working values. Write down the route of the shortest path from \(A\) to \(G\) and give its length. The track joining \(B\) and \(D\) is washed away in a flood. It is replaced by a new track of unknown length, \(x \mathrm {~km}\). \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_544_1271_1480_438}
2. What is the smallest value that \(x\) can take so that the route found in part (i) is still a shortest path? If the value of \(x\) is smaller than this, what is the weight of the shortest path from \(A\) to \(G\) ?
3. (a) For what values of \(x\) will vertex \(E\) have two temporary labels? Write down the values of these temporary labels.
   (b) For what values of \(x\) will vertex \(C\) have two temporary labels? Write down the values of these temporary labels. Dijkstra's algorithm has quadratic order.
4. If a computer takes 20 seconds to apply Dijkstra's algorithm to a complete network with 50 vertices, approximately how long will it take for a complete network with 100 vertices?

6 The arcs in the network represent the tracks in a forest. The weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-7_535_1267_395_440} Richard wants to walk along every track in the forest. The total weight of the arcs is \(26.7 + x\).

1. Find, in terms of \(x\), the length of the shortest route that Richard could use to walk along every track, starting at \(A\) and ending at \(G\). Show all of your working.
2. Now suppose that Richard wants to find the length of the shortest route that he could use to walk along every track, starting and ending at \(A\). Show that for \(x \leqslant 1.8\) this route has length \(( 32.4 + 2 x ) \mathrm { km }\), and for \(x \geqslant 1.8\) it has length \(( 34.2 + x ) \mathrm { km }\). Whenever two tracks join there is an information board for visitors to the forest. Shauna wants to check that the information boards have not been vandalised. She wants to find the length of the shortest possible route that starts and ends at \(A\), passing through every vertex at least once. Consider first the case when \(x\) is less than 3.2.
3. (a) Apply Prim's algorithm to the network, starting from vertex \(A\), to find a minimum spanning tree. Draw the minimum spanning tree and state its total weight. Explain why the solution to Shauna's problem must be longer than this.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), and show that it stalls before it has visited every vertex. Now consider the case when \(x\) is greater than 3.2 but less than 4.6.
4. (a) Draw the minimum spanning tree and state its total weight.
   (b) Use the nearest neighbour strategy, starting from vertex \(A\), to find a route from \(A\) to \(G\) passing through each vertex once. Write down the route obtained and its total weight. Show how a shortcut can give a shorter route from \(A\) to \(G\) passing through each vertex. Hence, explaining your method, find an upper bound for Shauna's problem.

1 Satellite navigation systems (sat navs) use a version of Dijkstra's algorithm to find the shortest route between two places. A simplified map is shown below. The values marked represent road distances, in km , for that section of road (from a place to a road junction, or between two places). \begin{figure}[h] \end{figure}

1. Use the map to construct a network with exactly 10 arcs to show the direct distances between these places, with no road junctions shown. For example, there will need to be an arc connecting \(A\) to \(B\) of weight 22, and also arcs connecting \(A\) to \(C , D\), and \(E\). There is no arc connecting \(A\) to \(F\) (because there is no route from \(A\) to \(F\) that does not pass through another place).
2. Apply Dijkstra's algorithm, starting at \(A\), to find the shortest route from \(A\) to \(F\). Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ).
3. If it takes 3 seconds for a certain sat nav to find the shortest route between two places when it has to process 200 places, calculate approximately how many minutes it will take when it has to process 4000 places.

5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres. \includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495} The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.

1. Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at \(M\).
2. Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish? Henry suggests that Jess only needs to visit each shop.
3. Apply the nearest neighbour method to the network, starting at \(M\), to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex? Henry thinks that Jess does not need to visit shop \(W\). He uses the table of shortest distances to list all the possible connections between \(M , N , P , R , S\) and \(V\) by increasing order of weight. Henry's list is given in your answer book.
4. Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for \(M , N , P , R , S , T\) and \(V\). Draw the tree and calculate its total weight. Jess insists that they must include shop \(W\).
5. Use the weight of the minimum spanning tree for \(M , N , P , R , S , T\) and \(V\), and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.

5 This question uses the same network as question 4. The total weight of the arcs in the network is 224. \includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(G\).
2. Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take to apply Dijkstra's algorithm to a network with 1400 vertices.
3. How much shorter would the path \(C E\) need to be for it to become part of a shortest path from \(A\) to \(G\) ? Following a landslip, the paths \(A C\) and \(C E\) become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.
4. Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex \(C\). Show your working.

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 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]

5 The network below represents a single-track railway system. The vertices represent stations, the arcs represent railway tracks and the weights show distances in km. The total length of the arcs shown is 60 km . \includegraphics[max width=\textwidth, alt={}, center]{d783915d-5950-4a97-b6a0-70959214e218-5_442_1152_429_459}

1. Apply Dijkstra's algorithm to the network, starting at \(G\), to find the shortest distance (in km ) from \(G\) to \(N\) and write down the route of this shortest path. Greg wants to travel from the station represented by vertex \(G\) to the station represented by vertex \(N\). He especially wants to include the track \(K L\) (in either direction) in his journey.
2. Show how to use your working from part (i) to find the shortest journey that Greg can make that fulfils his requirements. Write down his route. Percy Li needs to check each track to see if any maintenance is required. He wants to start and end at the station represented by vertex \(G\) and travel in one continuous route that passes along each track at least once. The direction of travel along the tracks does not matter.
3. Apply the route inspection algorithm, showing your working, to find the minimum distance that Percy will need to travel. Write down those arcs that Percy will need to repeat. If he travels this minimum distance, how many times will Percy travel through the station represented by vertex \(L\) ?

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\).

6 The diagram shows routes between points in a town. The distances are in kilometres. \includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-6_817_1219_319_422}

1. Use an appropriate algorithm to find a set of connecting arcs of minimum total length. Indicate your connecting arcs on the copy of the diagram in your answer book, and give their total length.
2. Give the name of the algorithm you have used, and describe it briefly.
3. Using the second diagram in your answer book, apply Dijkstra's algorithm to find the shortest distances from A to each of the other points. List the connections that are used, and give their total length.