7.04a Shortest path: Dijkstra's algorithm

2 Answer this question on the insert provided. Fig. 2 shows a network in which the weights on the arcs represent distances. \begin{figure}[h] \end{figure}

1. Apply Floyd's algorithm on the insert provided to find the complete network of shortest distances.
2. Show how to use your final matrices to find the shortest route from vertex \(\mathbf { 1 }\) to vertex 3, together with the length of that route.
3. Use the nearest neighbour algorithm, starting at vertex 1, to find a Hamilton cycle in the complete network of shortest distances. Give the corresponding cycle in the original network, together with its length.

5 Answer this question on the insert provided. Table 5 specifies a road network connecting 7 towns, A, B, \(\ldots\), G. The entries in Table 5 give the distances in miles between towns which are connected directly by roads. \begin{table}[h] \end{table}

1. Using the copy of Table 5 in the insert, apply the tabular form of Prim's algorithm to the network, starting at vertex A. Show the order in which you connect the vertices. Draw the resulting tree, give its total length and describe a practical application.
2. The network in the insert shows the information in Table 5. Apply Dijkstra's algorithm to find the shortest route from A to E. Give your route and its length.
3. A tunnel is built through a hill between A and B , shortening the distance between A and B to 6 miles. How does this affect your answers to parts (i) and (ii)?

2 The diagram shows an incomplete solution to the problem of using Dijkstra's algorithm to find a shortest path from \(A\) to \(F\). Any cell that has values in it is complete. \includegraphics[max width=\textwidth, alt={}, center]{a51b112d-1f3f-4214-94c1-8b9cd7eb831c-2_650_1246_1107_411}

1. (a) Find the missing weight on \(\operatorname { arc } B E\).
   (b) What can you deduce about the missing weight on arc \(C D\) ? You are now given that the weight of arc \(C E\) is not 3 .
2. (a) What can you deduce about the missing weight on arc \(C E\) ?
   (b) Complete the labelling of the boxes at \(E\) and \(F\) on the diagram in the Printed Answer Booklet. [2] Suppose that there are two shortest routes from \(A\) to \(F\).
3. Show how trace back is used to find the shortest routes from \(A\) to \(F\).

5 A rapid transport system connects 8 stations using three railway lines.
The blue line connects A to B to C to D . The red line connects \(B\) to \(F\) to \(E\) to \(D\). The green line connects E to G to H to A .

• The travel times for the return journeys are the same as for the outward journeys (so, for example, the travel time from B to A is 5 minutes, the same as the time from A to B ).
• All travel times include time spent stopped at stations.
• No trains are delayed so the travel times are all correct.
• Give a reason why the quickest journey from A to D may take longer than 12 minutes.

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

1. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
   (6)
2. State the shortest distance from A to G .
   (1)

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-006_412_1561_568_233}

1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from \(A\) to \(J\).
   (6 marks)
2. State the corresponding route.
   (1 mark)

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-05_412_1561_568_233}

1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from \(A\) to \(J\).
   (6 marks)
2. State the corresponding route.
   (1 mark)

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

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)

7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has 13 vertices and 24 edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges \(G K\) and \(L M\) are functions of \(x\) and \(y\), where \(x > 0 , y > 0\) and \(10 < x + y < 27\). \includegraphics[max width=\textwidth, alt={}, center]{f99fad35-3304-4e8f-be02-1439dfdc10e1-7_1218_1431_660_312} There are three routes from \(A\) to \(M\) of the same minimum total weight.

1. Use Dijkstra's algorithm on Figure 2 to find this minimum total weight.
2. Find the values of \(x\) and \(y\).

7 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows some of the main roads connecting Royton to London. The numbers on the edges represent the travelling times, in minutes, between adjacent towns. David lives in Royton and is planning to travel along some of the roads to a meeting in London. \includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-06_2196_1479_557_310}

1. 1. Use Dijkstra's algorithm on Figure 1 to find the minimum travelling time from Royton to London.
   2. Write down the route corresponding to this minimum travelling time.
2. On a particular day, before David leaves Royton, he knows that the road connecting Walsall and Marston is closed. Find the minimum extra time required to travel from Royton to London on this day. Write down the corresponding route.

3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road. \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}

1. 1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
2. 1. Use Dijkstra's algorithm on Figure 1 to find the shortest distance from \(A\) to \(J\).
   2. A new road, of length \(x \mathrm {~km}\), is built connecting \(I\) to \(J\). The minimum distance from \(A\) to \(J\) is reduced by using this new road. Find, and solve, an inequality for \(x\).

3 [Figure 1, printed on the insert, is provided for use in this question.]
The following network represents the footpaths connecting 12 buildings on a university campus. The number on each edge represents the time taken, in minutes, to walk along a footpath. \includegraphics[max width=\textwidth, alt={}, center]{eb305e75-0e85-4f99-8f04-27046a153532-03_899_1317_589_356}

1. 1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(A\) to \(L\).
   2. State the corresponding route.
2. A new footpath is to be constructed. There are two possibilities:
   from \(A\) to \(D\), with a walking time of 30 minutes; or from \(A\) to \(I\), with a walking time of 20 minutes. Determine which of the two alternative new footpaths would reduce the walking time from \(A\) to \(L\) by the greater amount.
   (3 marks)

3 The network below shows 11 towns, \(A , B , \ldots , K\). The number on each edge shows the time, in minutes, to travel between a pair of towns.

1. 1. Use Dijkstra's algorithm on the diagram below to find the minimum time to travel from \(A\) to \(K\).
   2. State the corresponding route.
2. On a particular day, Jenny travels from \(A\) to \(K\) but visits her friend at \(D\) on her way. Find Jenny's minimum travelling time.
3. On a different day, all roads connected to \(I\) are closed due to flooding. Jenny does not visit her friend at \(D\). Find her minimum time to travel from \(A\) to \(K\). State the route corresponding to this minimum time.
   [0pt] [2 marks] \section*{Answer space for question 3}
   \includegraphics[max width=\textwidth, alt={}]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-06_1478_1548_1213_239}

4 The network opposite shows roads connecting 10 villages, \(A , B , \ldots , J\). The time taken to drive along a road is not proportional to the length of the road. The number on each edge shows the average time, in minutes, to drive along each road.

1. A commuter wishes to drive from village \(A\) to the railway station at \(J\).
   1. Use Dijkstra's algorithm, on the diagram opposite, to find the shortest driving time from \(A\) to \(J\).
   2. State the corresponding route.
2. A taxi driver is in village \(D\) at 10.30 am when she receives a radio call asking her to pick up a passenger at village \(A\) and take him to the station at \(J\). Assuming that it takes her 3 minutes to load the passenger and his luggage, at what time should she expect to arrive at the station?
   [0pt] [2 marks]
   \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-09_2484_1717_223_150}

5 A fair comes to town one year and sets up its rides in two large fields that are separated by a river. The diagram shows the ten main rides, at \(A , B , C , \ldots , J\). The numbers on the edges represent the times, in minutes, it takes to walk between pairs of rides. A footbridge connects the rides at \(D\) and \(F\).

1. 1. Use Dijkstra's algorithm on the diagram below to find the minimum time to walk from \(A\) to each of the other main rides.
   2. Write down the route corresponding to the minimum time to walk from \(A\) to \(G\).
2. The following year, the fair returns. In addition to the information shown on the diagram, another footbridge has been built to connect the rides at \(E\) and \(G\). This reduces the time taken to travel from \(A\) to \(G\), but the time taken to travel from \(A\) to \(J\) is not reduced. The time to walk across the footbridge from \(E\) to \(G\) is \(x\) minutes, where \(x\) is an integer. Find two inequalities for \(x\) and hence state the value of \(x\). \section*{Answer space for question 5}
   1. (i) \includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-12_659_1591_1692_223}

7 Let the new value of \(i\) be \(i + 1\).

1. Apply the sorting algorithm to the list of numbers shown below. Record in the table provided the state of the list after each pass. Record the number of comparisons and the number of swaps that you make in each pass. (The result of the first pass has already been recorded.) List: \(\begin{array} { l l l l l l } 9 & 11 & 7 & 3 & 13 & 5 \end{array}\)
2. Suppose now that the list is split into two sublists, \(\{ 9,11,7 \}\) and \(\{ 3,13,5 \}\). The sorting algorithm is adapted to apply to three numbers, and is applied to each sublist separately. This gives \(\{ 7,9,11 \}\) and \(\{ 3,5,13 \}\). How many comparisons and swaps does this need?
3. How many further swaps would the original algorithm need to sort the revised list \(\{ 7,9,11,3,5,13 \}\) into increasing order? 3 The network below represents a number of villages together with connecting roads. The numbers on the arcs represent distances (in miles). \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-3_684_785_1612_625}

1. Use Dijkstra's algorithm to find the shortest routes from A to each of the other villages. Give these shortest routes and the corresponding distances. Traffic in the area travels at 30 mph . An accident delays all traffic passing through C by 20 minutes.
2. Describe how the network can be adapted and used to find the fastest journey time from A to F .

1 Five trainers, Ali, Bo, Chas, Dee and Eve, held an initial training session with each of four teams over an assault course. The completion times in minutes are recorded below. Each of the four teams is to be allocated a trainer and the overall time for the four teams is to be minimised. No trainer can train more than one team.

1. Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first then rows, to decide which four trainers should be allocated to which team. State the minimum total training time for the four teams using this matching.

2 Five successful applicants received the following scores when matched against suitability criteria for five jobs in a company. It is intended to allocate each applicant to a different job so as to maximise the total score of the five applicants.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(15 - x\).
2. Form a new table by subtracting each number in the table from 15. Use the Hungarian algorithm to allocate the jobs to the applicants so that the total score is maximised.
3. It is later discovered that Bill has already been allocated to Job 4. Decide how to alter the allocation of the other jobs so as to maximise the score now possible.

2 The following table shows the times taken, in minutes, by five people, Ash, Bob, Col, Dan and Emma, to carry out the tasks 1, 2, 3 and 4 . Dan cannot do task 3. Each of the four tasks is to be given to a different one of the five people so that the overall time for the four tasks is minimised.

1. Modify the table of values by adding an extra row of non-zero values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first then rows, to decide which four people should be allocated to which task. State the minimum total time for the four tasks using this matching.
3. After special training, Dan is able to complete task 3 in 12 minutes. Determine, giving a reason, whether the minimum total time found in part (b) could be improved.
   (2 marks)

1 The times taken in minutes for five people, \(\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }\) and T , to complete each of five different tasks are recorded in the table. Using the Hungarian algorithm, each of the five people is to be allocated to a different task so that the total time for completing the five tasks is minimised.

1. By reducing the columns first and then the rows, show that the new table of values is as follows.

   3	5	3	0	1
   6	4	3	2	0
   3	5	4	1	0
   3	2	3	0	1
   0	0	0	1	1

2. Show that the zeros in the table in part (a) can be covered with three lines, and use adjustments to produce a table where five lines are required to cover the zeros.
3. Hence find the two possible ways of allocating the five people to the five tasks so that the total completion time is minimised.
4. Find the minimum total time for completing the five tasks.

2 Four of the five students Phil, Quin, Ros, Sue and Tim are to be chosen to make up a team for a mathematical relay race. The team will be asked four questions, one each on the topics A, B, C and D. A different member of the team will answer each question. Each member has to give the correct answer to the question before the next question is asked. The team with the least overall time wins.
The average times, in seconds, for each student in some practice questions are given below.

1. Modify the table of values by adding an extra row of values so that the Hungarian algorithm can be applied.
2. Use the Hungarian algorithm, reducing columns first, then rows, to decide which four students should be chosen for the team. State which student should be allocated to each topic and state the total time for the four students on the practice questions using this matching.

2 The daily costs, in pounds, for five managers A, B, C, D and E to travel to five different centres are recorded in the table below. Using the Hungarian algorithm, each of the five managers is to be allocated to a different centre so that the overall total travel cost is minimised.

1. By reducing the rows first and then the columns, show that the new table of values is

   3	6	3	6	0
   4	0	6	0	2
   6	4	3	6	0
   2	3	8	3	0
   0	2	0	0	2

2. Show that the zeros in the table in part (a) can be covered with three lines and use adjustments to produce a table where five lines are required to cover the zeros.
3. Hence find the two possible ways of allocating the five managers to the five centres with the least possible total travel cost.
4. Find the value of this minimum daily total travel cost.

2 The following table shows the scores of five people, Alice, Baji, Cath, Dip and Ede, after playing five different computer games. Each of the five games is to be assigned to one of the five people so that the total score is maximised. No person can be assigned to more than one game.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(20 - x\).
2. Form a new table by subtracting each number in the table above from 20, and hence show that, by reducing columns first and then rows, the resulting table of values is as below.

   3	1	1	1	0
   0	4	5	2	2
   4	0	5	0	7
   5	1	0	1	1
   5	1	0	2	5

3. Show that the zeros in the table in part (b) can be covered with one horizontal and three vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. Hence find the possible allocations of games to the five people so that the total score is maximised.
5. State the value of the maximum total score.