7.04a Shortest path: Dijkstra's algorithm

3. \begin{figure}[h] \end{figure} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the rninimax route.

1. Complete the table in the answer booklet.
   (8)
2. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route.
   (2)

6. The table below shows the distances, in km, between six towns \(A , B , C , D , E\) and \(F\).

1. Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected.
   (4)
2. 1. Using your answer to part (a) obtain an initial upper hound for the solution of the travelling salesman problem.
   2. Use a short cut to reduce the upper bound to a value less than 680 .
      (4)
3. Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem.
   (4)

7. \includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516} The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

1. Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
2. Use your answer to part (a) to determine an initial upper bound for the length of the route.
3. Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
4. Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
5. By deleting C, and all of its arcs, find a lower bound for the length of the route.
6. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
   (2) (Total 16 marks)

2.

1. Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\), and F .

   	A	B	C	D	E	F
   A	-	77	34	56	67	21
   B	77	-	58	58	36	74
   C	34	58	-	73	70	42
   D	56	58	73	-	68	38
   E	67	36	70	68	-	71
   F	21	74	42	38	71	-

   Rachel must visit each collection point. She will start and finish at A and wishes to minimise the total distance travelled.
2. Starting at A, use the nearest neighbour algorithm to obtain an upper bound. Make your method clear. Starting at B, a second upper bound of 293 km was found.
3. State the better upper bound of these two, giving a reason for your answer. By deleting A, a lower bound was found to be 245 km .
4. By deleting B, find a second lower bound. Make your method clear.
5. State the better lower bound of these two, giving a reason for your answer.
6. Taking your answers to (c) and (e), use inequalities to write down an interval that must contain the length of Rachel's optimal route.
   

1. The table below shows the least costs, in pounds, of travelling between six cities, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
   (2)
2. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
   (1)
3. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
4. State the best upper bound from your answers to (b) and (c).
5. Starting by deleting A , and all of its arcs, find a lower bound for the route length.
   

1. \begin{figure}[h] \end{figure} The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances in your answer book.
2. Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou's route. Write down the route which gives this upper bound.
3. Starting by deleting A, and all of its arcs, find a lower bound for the route length.

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
2. On Diagram 1 and Diagram 2 in the answer book, add a supersource S and a supersink T . On Diagram 1, show the minimum capacities of the arcs you have added.
3. Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values on the arcs to S and T and on \(\operatorname { arcs } \mathrm { CD }\), DE , DG , FG, FI and GI.
4. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
5. Show your maximum flow on Diagram 3 in the answer book.
6. Prove that your flow is maximal.

3. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
2. State the capacity of cut \(\mathrm { C } _ { 1 }\). The labelling procedure has been used and the result drawn on Diagram 1 in the answer book.
3. Use Diagram 1 to find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
   (4)
4. Draw a maximum flow pattern on Diagram 2 in your answer book.
   (2)
5. Prove that the flow shown in (d) is maximal.
   (2)

5. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed, network. The capacity of each arc is shown on that arc and the numbers in circles represent an initial flow from S to T . Two cuts, \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown on Figure 1.

1. Find the capacity of each of the two cuts and the value of the initial flow.
   (3)
2. Complete the initialisation of the labelling procedure on Figure 1 in the answer book, by entering values along \(\mathrm { SB } , \mathrm { AB } , \mathrm { BE }\) and BG .
   (2)
3. Hence use the labelling procedure to find a maximum flow of 85 through the network. You must list each flow-augmenting path you use, together with its flow.
   (5)
4. Show your flow pattern on Figure 2.
   (2)
5. Prove that your flow is maximal.
   (2)

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\), and \(z\).
   (3)
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

6. \begin{figure}[h] \end{figure} A maximin route is to be found through the network shown in Figure 3.
Complete the table in the answer book, and hence find a maximin route.

2

1. Set up a dynamic programming tabulation to find the maximum weight route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-3_595_1054_404_587} Give the route and its total weight.
2. The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.

   Activity	Duration	Immediate predecessors
   \(A\)	8	-
   \(B\)	9	-
   C	7	-
   D	5	\(A\)
   E	6	\(A\)
   \(F\)	4	\(B\)
   \(G\)	5	B
   \(H\)	6	\(B\)
   \(I\)	10	C
   \(J\)	9	\(C\)
   \(K\)	6	\(C\)
   \(L\)	7	D, F, I
   \(M\)	6	\(E , G , J\)
   \(N\)	8	\(H\), \(K\)

   Make a large copy of the network with the activities \(A\) to \(N\) labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
3. Compare the solutions to parts (i) and (ii).

4 The network represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). The weights on the arcs represent pipe capacities in gallons per minute. \includegraphics[max width=\textwidth, alt={}, center]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-6_597_1577_404_283}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
2. Explain why the \(\operatorname { arcs } A C\) and \(A D\) cannot both be full to capacity and why the \(\operatorname { arcs } D F\) and \(E F\) cannot both be full to capacity.
3. Draw a diagram to show a flow in which as much as possible flows through vertex \(E\) but none flows through vertex \(A\) and none flows through vertex \(D\). State the maximum flow through vertex \(E\). An engineer wants to find a flow augmenting route to improve the flow from part (iii).
4. (a) Explain why there can be no flow augmenting route that passes through vertex \(A\) but not through vertex \(D\).
   (b) Write down a flow augmenting route that passes through vertex \(D\) but not through vertex \(A\). State the maximum by which the flow can be augmented.
5. Prove that the augmented flow in part (iv)(b) is the maximum flow.
6. A vertex restriction means that the flow through \(E\) can no longer be at its maximum rate. By how much can the flow through \(E\) be reduced without reducing the maximum flow from \(S\) to \(T\) ? Explain your reasoning. The pipe represented by the arc \(B E\) becomes blocked and cannot be used.
7. Draw a diagram to show that, even when the flow through \(E\) is reduced as in part (vi), the same maximum flow from \(S\) to \(T\) is still possible.

2 The network models a cooling system in a factory. Coolant starts at \(A , B\) and \(C\) and flows through the system. The arcs model components of the cooling system and the weights show the maximum amount of coolant that can flow through each component of the system (measured in litres per second). The arrows show the direction of flow. \includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-3_611_832_539_605}

1. Add a supersource, \(S\), and a supersink, \(T\), to the copy of the network in your answer book. Connect \(S\) and \(T\) to the network using appropriately weighted arcs.
2. (a) Find the capacity of the cut that separates \(A , B , C\) and \(E\) from \(D , F , G\) and \(H\).
   (b) Find the capacity of the cut that separates \(A , B , C , D , E\) and \(F\) from \(G\) and \(H\).
   (c) What can you deduce from this value about the maximum flow through the system?
3. Find the maximum possible flow through the system and prove that this is the maximum.
4. Describe what effect increasing the capacity of \(C E\) would have on the maximum flow.

3 Each of five jobs is to be allocated to one of five workers, and each worker will have one job. The table shows the cost, in \(\pounds\), of using each worker on each job. It is required to find the allocation for which the total cost is minimised. Worker \begin{table}[h] \end{table}

1. Construct a reduced cost matrix by first reducing rows and then reducing columns. Cross through the 0's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [Try to ensure that the values in your table can still be read.]
2. Augment your reduced cost matrix and hence find a minimum cost allocation. Write a list showing which job should be given to which worker for your minimum cost allocation, and calculate the total cost in this case. Gill decides that she does not like the job she has been allocated and increases her cost for this job by \(\pounds 100\). New minimum cost allocations can be found, each allocation costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii).
3. Use the grid in your answer book to show the positions of the 0 's and 1 's in the augmented reduced cost matrix from part (ii). Hence find three allocations, each costing just \(\pounds 1\) more than the minimum cost allocation found in part (ii) and with Gill having a different job to the one allocated in part (ii). [5]

6 The table below shows an incomplete dynamic programming tabulation to solve a maximin problem. Do not write your answer on this copy of the table.

1. Complete the working and suboptimal maximin columns on the copy of the table in your answer book.
2. Use your answer to part (i) to write down the maximin value and the corresponding route. Give your route using (stage; state) variables.
3. Draw the network that is represented in the table. The network represents a system of pipes and the arc weights show the capacities of the pipes, in litres per second.
4. What does the answer to part (ii) represent in this network? The weights of the arcs in the maximin route are each reduced by the maximin value and then a maximin is found for the resulting network. This is done until the maximin value is 0 . At this point the network is as shown below. \includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-8_552_1474_438_274}
5. (a) Describe how this solves the maximum flow problem on the original network.
   (b) Draw this maximum flow and draw a cut with value equal to the value of the flow. \section*{END OF QUESTION PAPER} \section*{\(\mathrm { OCR } ^ { \text {勾 } }\)}

3 A team triathlon is a race involving swimming, cycling and running for teams of three people. The first person swims, then the second person cycles and finally the third person runs. The winning team is the team that completes all three stages of the triathlon in the shortest time. Four friends are training to enter as a team for the triathlon. They need to choose who to enter for each stage of the triathlon, and who to leave out (this person will be the reserve). The table shows the times, in minutes, for each of them to complete each stage in training.

1. Complete a dummy column in the table in your answer book. Apply the Hungarian algorithm, reducing columns first. Make sure that the values in your tables can all be seen. Write a list showing who should be chosen for each stage of the triathlon. What is the minimum total time in which the team can expect to complete the three stages of the triathlon? The day before the triathlon, the friend who had been chosen to swim is injured and cannot compete.
2. If the reserve takes over the swim, how much longer can the team expect the triathlon to take?
3. Remove the row corresponding to the injured swimmer to form a \(3 \times 3\) table. Apply the Hungarian algorithm to find who should be chosen for each stage to complete the triathlon in the minimum expected time. State the minimum expected time.

4 Jeremy is planning a long weekend break during which he wants to photograph as many different churches as he can. He will start from his home, \(J\), on Friday morning and return to his home on Monday evening. Table 1, below, summarises the routes he can take each day and the number of churches that he will pass on each route. You may assume that the 28 churches in the table are all different. \begin{table}[h] \end{table}

1. Represent the information in the table as a directed network in which the vertices represent the places. You may code the place names using the letters, as above. Jeremy wants to use dynamic programming to find the route on which he will pass the greatest number of churches. The (stage; state) variables will represent the places where he stays overnight. \(J\) will have (stage; state) variable ( \(0 ; 0\) ) at the start of the journey and ( \(4 ; 0\) ) at the end. Table 2 shows the (stage; state) variables for all the other places. \begin{table}[h]

   Place	\(K\)	\(L\)	\(M\)	\(N\)	\(P\)	\(R\)	\(S\)	\(T\)
   Stage variable	1	1	2	2	2	3	3	3
   State variable	0	1	0	1	2	0	1	2

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Set up a dynamic programming tabulation, working backwards from Monday to Friday, to find the route that Jeremy should take to pass the greatest number of churches. Write down Jeremy's route. You may code the place names using the letters, as above. Write down the number of churches that he will be able to photograph on this route.

5 The diagram shows a flow through a network of directed arcs. The amount that can flow in each arc is limited by its upper capacity, and the lower capacity of each arc is 0 . The labelled arrows by the arcs show how much more (excess capacity) and how much less (potential backflow) could flow in each arc, in litres per second, and the objective is to find the maximum flow from \(S\) to \(T\). \includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-6_969_1363_459_351}

1. How many litres per second are currently flowing along the route SACHT?
2. How many litres per second are currently flowing from \(S\) to \(T\) ?
3. What is the maximum by which the flow along the route SBGIT can be increased? Use the copy of the network in your answer book to show what happens to the labels on the arrows when the flow along this route is augmented by this amount.
4. Find the maximum amount that can flow through the network. Explain, by using a cut, how you know that your flow is a maximum. The network had vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\). The single vertex \(E\) is replaced by the pair of vertices \(E _ { 1 }\) and \(E _ { 2 }\), together with the \(\operatorname { arc } E _ { 1 } E _ { 2 }\).
5. What does the \(\operatorname { arc }\) joining \(E _ { 1 }\) and \(E _ { 2 }\) tell you about the flow at \(E\) ?
6. Complete the diagram in your answer book to show the flow resulting after part (iii) on a directed network with vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\).

2 Water flows through pipes from an underground spring to a tap. The size of each pipe limits the amount that can flow. Valves restrict the direction of flow. The pipes are modelled as a network of directed arcs connecting a source at \(S\) to a sink at \(T\). Arc weights represent the (upper) capacities, in litres per second. Pipes may be empty. Fig. 3 shows a flow of 5 litres per second from \(S\) to \(T\). Fig. 4 shows the result of applying the labelling procedure to the network with this flow. The arrows in the direction of potential flow show excess capacities (how much more could flow in the arc, in that direction) and the arrows in the opposite direction show potential backflows (how much less could flow in the arc). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down the capacity of \(\operatorname { arc } F T\) and of \(\operatorname { arc } D T\). Find the value of the cut that separates the vertices \(S , A , B , C , D , E , F\) from the sink at \(T\).
2. (a) Update the excess capacities and the potential backflows to show an additional flow of 2 litres per second along \(S - C - B - F - T\).
   (b) Write down a further flow augmenting route and the amount by which the flow can be augmented. You do not need to update the excess capacities and potential backflows a second time.
3. Show the flow that results from part (ii)(b) and find a cut that has the same value as your flow.

3 A theatre company needs to employ three technicians for a performance. One will operate the lights, one the sound system and one the flying trapeze mechanism. Four technicians have applied for these tasks. The table shows how much it will cost the theatre company, in £, to employ each technician for each task. The theatre company wants to employ the three technicians for whom the total cost is least.
The Hungarian algorithm is to be used to find the minimum cost allocation, but before this can be done the table needs to be modified.

1. Make the necessary modification to the table. Working from your modified table, construct a reduced cost matrix by first reducing rows and then reducing columns. You should show the amount by which each row has been reduced in the row reductions and the amount by which each column has been reduced in the column reductions. Cross through the 0 's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [You must ensure that the values in your table can still be read.]
2. Complete the application of the Hungarian algorithm to find a minimum cost allocation. Write a list showing which technician should be employed for each task. Calculate the total cost to the theatre company. Although Amir put in the lowest cost for operating the lighting, you should have found that he has not been allocated this task. Amir is particularly keen to be employed to operate the lights so is prepared to reduce his cost for this task.
3. Find a way to use two of Bex, Caz and Dee to operate the sound effects and the flying trapeze mechanism at the lowest cost. Hence find what Amir's new cost should be for the minimum total cost to the theatre company to be exactly \(\pounds 1\) less than your answer from part (ii).

6 The table below shows an incomplete dynamic programming tabulation to solve a maximum path problem.

1. Complete the working and suboptimal maximum columns on the copy of the table in your Answer Book. Write down the weight of the maximum path and the corresponding route. Give your route using (stage; state) variables. Ken has entered a cake-making competition. The actions in the dynamic programming tabulation above represent the different types of cake that Ken could make. Each competitor must make one cake in each stage of the competition. The rules of the competition mean that, for each competitor, the actions representing their four cakes must form a route from \(( 0 ; 0 )\) to \(( 4 ; 0 )\). The weights in the tabulation are the number of points that Ken can expect to get by making each of the cakes. Each cake is also judged for how well it has been decorated. The number of points that Ken expects to get for decorating each cake is shown below. Ken is not very good at decorating the cakes. He expects to get 0 points for decorating for the cakes that are not listed below.

   Cake	(0; 0) to (1; 0)	(1; 0) to (2; 1)	(1; 1) to (2; 0)	(2; 0) to (3; 0)	(2; 0) to (3; 1)	(2; 1) to (3; 0)	(2; 1) to (3; 1)
   Decorating points	1	1	2	1	1	1	1

2. Calculate the number of decorating points that Ken can expect if he makes the cakes given in the solution to part (i). When Ken meets the other competitors he realises that he is not good enough to win the competition, so he decides instead to try to win the judges' special award. For each cake, the absolute difference between the score for cake-making and the score for decorating is calculated. The award is given to the person whose biggest absolute difference is least. (Note: to find the absolute difference, calculate larger number-smaller number, or 0 if they are the same.)
3. Draw the graph that the dynamic programming tabulation represents. Label the vertices using (stage; state) labels with \(( 0 ; 0 )\) at the left hand side and \(( 4 ; 0 )\) at the right hand side. Make the graph into a network by weighting the arcs with the absolute differences.
4. Use a dynamic programming tabulation to find the minimax route for the absolute differences.

1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.

• Arthur wants to use lavender, orange or tangerine.
• Bridget wants to use lavender, mauve or pink.
• Carlos wants to use pink or scarlet.
• Davinder wants to use mauve or pink.
• Eric wants to use lavender or orange.
• Ffion wants to use mauve.

Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.

1. Draw a bipartite graph on the insert, showing which neighbours ( \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
2. By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
3. Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)

2 A company has organised four regional training sessions to take place at the same time in four different cities. The company has to choose four of its five trainers, one to lead each session. The cost ( \(\pounds 1000\) 's) of using each trainer in each city is given in the table.

1. Convert this into a square matrix and then apply the Hungarian algorithm, reducing rows first, to allocate the trainers to the cities at minimum cost.
2. Betty discovers that she is not available on the date set for the training. Find the new minimum cost allocation of trainers to cities.

3 [Answer this question on the insert provided.]
A flying doctor travels between islands using small planes. Each flight has a weight limit that restricts how much he can carry. A plague has broken out on Farr Island and the doctor needs to take several crates of medical supplies to the island. The crates must be carried on the same planes as the doctor. The diagram shows a network with (stage; state) variables at the vertices representing the islands, arcs representing flight routes that can be used, and weights on the arcs representing the number of crates that the doctor can carry on each flight. \begin{figure}[h] \end{figure} Stage 1 Stage 2

1. It is required to find the route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) for which the minimum number of crates that can be carried on any stage is a maximum (the maximin route). The insert gives a dynamic programming tabulation showing stages, states and actions, together with columns for working out the route minimum at each stage and for indicating the current maximin. Complete the table on the insert sheet and hence find the maximin route and the maximum number of crates that can be carried.
2. It is later found that the number of crates that can be carried on the route from ( \(2 ; 0\) ) to ( \(3 ; 0\) ) has been recorded incorrectly and should be 15 instead of 5 . What is the maximin route now, and how many crates can be carried?