7.04a Shortest path: Dijkstra's algorithm

3 The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. Distance Matrix

\(\mathbf { 4 }\) & 9 & 7 & 6 & 12
\hline Route Matrix Fig. 3.1 \begin{figure}[h] \end{figure}

1. Draw the complete network of shortest distances.
2. Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \begin{table}[h]

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	1	2	3	4
   5	-	3	-	1

   \captionsetup{labelformat=empty} \caption{Fig. 3.3}
   \end{table}
3. Draw the extended network and the complete 5 -node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.)
4. Produce the shortest distance matrix and the route matrix for the extended 5-node network.
5. Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network.
6. By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm.
7. In the original 5-node network find a shortest route starting at vertex \(\mathbf { 1 }\) and using each of the 6 arcs at least once. Give the length of your route. 4 Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10 ml of oil and between 3 and 6 ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar. Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil: $$\begin{array} { l c } \text { Maximise } & \frac { x } { x + y } \\ \text { subject to } & 0 \leqslant x \leqslant 10 , \\ & 0 \leqslant y \leqslant 6 , \\ & x - 2 y \leqslant 0 . \end{array}$$

1. Explain why this problem is not an LP.
2. Use the simplex method to solve the following LP. $$\begin{array} { l c } \text { Maximise } & x - y \\ \text { subject to } & 0 \leqslant x \leqslant 10 \\ & 0 \leqslant y \leqslant 6 \\ & x - 2 y \leqslant 0 \end{array}$$
3. Kassi prefers to have more vinegar than oil. She formulates the following LP. $$\begin{array} { l l } \text { Maximise } & y - x \\ \text { subject to } & 5 \leqslant x \leqslant 10 , \\ & 3 \leqslant y \leqslant 6 , \\ & x - 2 y \leqslant 0 . \end{array}$$ Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii).
4. Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii).
5. Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem. Explain briefly how to proceed.

3 Floyd's algorithm is applied to the following network: \includegraphics[max width=\textwidth, alt={}, center]{483a681e-011a-464f-b7cb-007d894d1516-3_398_394_331_833} At the end of the third iteration of the algorithm the distance and route matrices are as follows:

1. Perform the fourth (final) iteration of the algorithm.
2. Explain how to use the final matrices to find the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex \(\mathbf { 3 }\), and give the distance and route.
3. Draw the complete network of shortest distances.
4. Apply the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to your complete network of shortest distances. Give the Hamilton cycle it produces, its length, and the corresponding route through the original network.
5. By considering vertex 2 and its arcs, construct a lower bound for the length of the solution to the travelling salesperson problem in the original network.
6. Explain what you can deduce from your answers to parts (iv) and (v). 4 Noel is designing a hotel patio. It will consist of decking and paving.
   Decking costs \(\pounds 4\) per \(\mathrm { m } ^ { 2 }\) and paving costs \(\pounds 2\) per \(\mathrm { m } ^ { 2 }\). He has a budget of \(\pounds 2500\).
   Noel prefers paving to decking, and he wants the area given to paving to be at least twice that given to decking. He wants to have as large a patio as possible.
   Noel's problem is formulated as the following LP.
   Let \(x\) be the number of \(\mathrm { m } ^ { 2 }\) of decking.
   Let \(y\) be the number of \(\mathrm { m } ^ { 2 }\) of paving. $$\begin{aligned} \text { Maximise } \quad P & = x + y \\ \text { subject to } 2 x + y & \leqslant 1250 \\ 2 x - y & \leqslant 0 \\ x & \geqslant 0 \\ y & \geqslant 0 \end{aligned}$$

1. Use the simplex algorithm to solve this LP. Pivot first on the positive element in the \(y\) column. Noel would like to have at least \(200 \mathrm {~m} ^ { 2 }\) of decking.
2. Add a line corresponding to this constraint to your solution tableau from part (i), and modify the resulting table either for two-stage simplex or the big-M method. Hence solve the problem. Noel finally decides that he will minimise the annual cost of maintenance, which is given by \(\pounds ( 0.75 x + 1.25 y )\), subject to the additional constraint that there is at least \(1000 \mathrm {~m} ^ { 2 }\) of patio.
3. Starting from your solution to part (ii), use simplex to solve this problem.

3 The weights on the network represent distances. \includegraphics[max width=\textwidth, alt={}, center]{88acde67-e22b-478a-9145-48abe931beff-3_401_702_315_683}

1. 1. Apply Floyd's algorithm to the network to find the complete network of shortest distances, showing that the final matrices are as follows.

      \cline { 2 - 5 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)
      \(\mathbf { 1 }\)	22	14	11	23
      \(\mathbf { 2 }\)	14	28	15	27
      \(\mathbf { 3 }\)	11	15	22	12
      \(\mathbf { 4 }\)	23	27	12	24

Draw the complete network of shortest distances.
(ii) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
(iii) By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
(b) Solve the route inspection problem in the original network, and say how you can be sure that your solution is optimal. 4 A factory's output includes three products. To manufacture a tonne of product \(\mathrm { A } , 3\) tonnes of water are needed. Product B needs 2 tonnes of water per tonne produced, and product C needs 5 tonnes of water per tonne produced. Product A uses 5 hours of labour per tonne produced, product B uses 6 hours and product C uses 2 hours. There are 60 tonnes of water and 50 hours of labour available for tomorrow's production.

1. Formulate a linear programming problem to maximise production within the given constraints.
2. Use the simplex algorithm to solve your LP, pivoting first on your column relating to product C.
3. An extra constraint is imposed by a contract to supply at least 8 tonnes of A . Use either two stage simplex or the big M method to solve this revised problem.

4 The diagram shows routes connecting five cities. Lengths are in km . \includegraphics[max width=\textwidth, alt={}, center]{ae8dc840-0c61-4ba5-b082-1f5f3e6c2cef-4_442_995_319_534}

1. Produce the initial matrices for an application of Floyd's algorithm to find the complete network of shortest distances between the five cities. The following are the distance and route matrices after the third iteration of Floyd's algorithm.

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)
   \(\mathbf { 1 }\)	44	22	42	15	15
   \(\mathbf { 2 }\)	22	44	20	5	23
   \(\mathbf { 3 }\)	42	20	40	25	43
   \(\mathbf { 4 }\)	15	5	25	10	16
   \(\mathbf { 5 }\)	15	23	43	16	30

(ii) Perform the fourth iteration. There are no changes on the fifth iteration, so your answer to part (ii) should give the complete network of shortest distances.
(iii) Use your matrices to find the shortest distance and route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 1 }\), and explain how you do it.
(iv) Draw the complete network of shortest distances, not including the loops.
(v) Apply the nearest neighbour algorithm to your network in part (iv), starting at vertex 2. Give the length of the Hamilton cycle that is produced. Interpret the Hamilton cycle in terms of the original diagram and state what the algorithm has achieved. }{www.ocr.org.uk}) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.
For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1PB.
OCR is part of the

2 The network is a representation of a show garden. The weights on the arcs give the times in minutes to walk between the six features represented by the vertices, where paths exist. \includegraphics[max width=\textwidth, alt={}, center]{c3a528e4-b5fe-4bff-a77e-e3199bb225a1-3_483_985_342_539}

1. Why might it be that the time taken to walk from vertex \(\mathbf { 2 }\) to vertex \(\mathbf { 3 }\) via vertex \(\mathbf { 4 }\) is less than the time taken by the direct route, i.e. the route from \(\mathbf { 2 }\) to \(\mathbf { 3 }\) which does not pass through any other vertices? The matrices shown below are the results of the first iteration of Floyd's algorithm when applied to the network.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)	\(\mathbf { 6 }\)
   \(\mathbf { 1 }\)	\(\infty\)	15	\(\infty\)	\(\infty\)	7	8
   \(\mathbf { 2 }\)	15	30	6	2	6	23

2 A government has just created a new ministry, the Ministry of Administrative Affairs. The ministry is to have four departments:
the Administration
the Bureaucracy
the Certification Service
the Duplication Section.
Each of these departments is to be established in a separate office on one of four existing sites. The diagram shows the direct journey times in minutes between these four sites. \includegraphics[max width=\textwidth, alt={}, center]{52b8153f-e655-4852-a0f8-6f1c1e9c9170-3_342_403_721_829}

1. Use Floyd's algorithm to find the shortest journey times between the four office sites.
2. Draw a network showing your shortest times.
3. Use appropriate algorithms to find upper and lower bounds for the optimum solution to the Travelling Salesperson Problem in the original network, briefly explaining the steps taken.
4. A van is to be organised to deliver bundles of paperwork between the departments. Why might the optimum solution to the TSP be useful in planning this, and why might it not be?
5. Journeys to locations 2 and 3, from locations 1 and 4, are subject to a congestion charge which is equivalent in costing terms to 15 minutes of journey time. What sort of network would be needed to model this?

3 The weights on the network represent distances. \includegraphics[max width=\textwidth, alt={}, center]{eb4e9c34-7d8f-4118-b7ec-edcd9567077f-4_451_544_324_740}

1. The answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 5 }\).
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Using the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 5 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
3. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
4. Interpret your Hamilton cycle in part (iii) in terms of the original network.
5. Give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Give the length of your walk.

3 Five towns, 1, 2, 3, 4 and 5, are connected by direct routes as shown. The arc weights represent distances. \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-4_632_540_312_744}

1. The printed answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex 5 to vertex 2.
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 4 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
3. Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
4. Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
5. Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
6. Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.

3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times. \includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \end{table}

\(\mathbf { 4 }\) & 10 & 5 & 7 & 10
\hline \end{tabular} \end{center} \end{table} \begin{table}[h] \end{table}

1. Draw the complete network of shortest times.
2. Explain how to use the final route matrix to find the quickest route from node \(\mathbf { 4 }\) to node \(\mathbf { 1 }\) in the original incomplete network. Give this quickest route. A new node, node 5, is added to the original incomplete network. The new journey times are shown in the table. \begin{center} \begin{tabular}{ | l | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\) \hline

\(\mathbf { 5 }\) & 4 & - & - & 2
\hline

1. Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
2. Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
3. (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
   (B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
4. By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
5. In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables.

   Driving times	to A	to W
   From G	20 min	15 min

   \multirow{2}{*}{Train journey}	To V			To LB
   	normal time	probability of delay	delay	normal time	probability of delay	delay
   From A	1 hr 40 min	0.05	10 min	1 hr 45 min	0.05	10 min
   From W	1 hr 30 min	0.10	20 min	1 hr 35 min	0.10	20 min

   \multirow{2}{*}{ Tube journey }	To KC
   \cline { 2 - 4 }	normal time	probability of delay	delay
   From V	7 min	0.20	2 min
   From LB	9 min	0.10	2 min

   Helen wants to choose the route which will give the shortest expected journey time.
6. Draw a decision tree to model Helen's decisions and the possible outcomes.
7. Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
8. Find the value of the radio information, explaining your calculation.
9. Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?

1. Perform the fourth iteration of the algorithm, and show that there is no change to either matrix in the final iteration.
2. Show how to use the matrices to give the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex 2.
3. Draw the complete network of shortest distances.
4. Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
5. By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The network in Figure 3 shows the distances, in miles, between a newspaper distributor based at area \(A\), and five areas, \(B , C , D , E\), and \(F\), to which the distributor must deliver newspapers. Each morning a delivery van has to set out from \(A\) and visit each of these areas before again returning to \(A\), and the driver wishes to keep the total mileage to a minimum.

1. Draw a complete network showing the shortest distances between the six areas.
   (3 marks)
2. Obtain a minimum spanning tree for the complete network and hence find an upper bound for the length of the driver's route.
   (5 marks)
3. Improve this upper bound to find an upper bound of less than 55 miles.
4. By deleting \(A\), find a lower bound for the total length of the route.

1. This question should be answered on the sheet provided.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the distances, in miles, between the five villages in which Sarah is planning to enquire about holiday work, with village \(A\) being Sarah's home village.

1. Illustrate this situation as a complete network showing the shortest distances.
   (2 marks)
2. Use the nearest neighbour algorithm, starting with \(A\), to find an upper bound to the length of a tour beginning and ending at \(A\).
   (2 marks)
3. Interpret the tour found in part (b) in terms of the original network.
   (2 marks)
   

7. This question should be answered on the sheet provided. A tinned food producer delivers goods to six supermarket warehouses, \(B , C , D , E , F\) and \(G\), from its base, \(A\). The distances, in kilometres, between each location are given in the table below. \section*{Please hand this sheet in for marking}

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.

1. By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
   (2 marks)
2. Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
3. Interpret the tour found in part (b) in terms of the original network.

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A band is going on tour to play gigs in six towns, including their home town, \(A\). The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at \(A\) and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.

1. By inspection, draw a complete network showing the shortest distances between the towns.
2. Use your complete network and the nearest neighbour algorithm, starting at \(A\), to find an upper bound for the total distance travelled.
3. 1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
   2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
4. By deleting \(A\), find a lower bound for the total distance travelled.
5. State an interval of as small a width as possible within which \(d\), the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}

   Stage	Previous tournament	Current tournament
   \multirow[t]{3}{*}{1}	G	J K L
   	\(H\)	J K L
   	I	J K L
   \multirow[t]{3}{*}{2}	D	G H I
   	\(E\)	G H I
   	\(F\)	G H I
   \multirow[t]{3}{*}{3}	A	D E F
   	\(B\)	D E F
   	C	D E F
   4	None	A B C

   \section*{Please hand this sheet in for marking}
   1. \includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
   2. \section*{Sheet for answering question 6 (cont.)}
   3. 2. \(\_\_\_\_\)
   5. \(\_\_\_\_\)

4 The table shows the activities involved in a project, their durations in hours and their immediate predecessors. The activities can be represented as an activity network.

1. Use standard algorithms to find the activities that form
   You must show working to demonstrate the use of the algorithms. Only one of the paths from part (a) has a practical interpretation.
2. What is the practical interpretation of the total weight of that path? The duration of activity E can be changed. No other durations change.
3. What is the smallest increase to the duration of E that will make activity E become part of a longest path through the network?

6 Eight footpaths connect six villages. The lengths of these footpaths, in km , are given in the table.

1. The shortest route from B to C using these footpaths has length 10 km . Without using an algorithm, write down this shortest route from B to C.
2. Use an appropriate algorithm to find the shortest route from A to F .
3. Write down all the pairs of villages for which the shortest route between them uses at least one footpath that is not in the minimum spanning tree for the six villages.

2 A network is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c9fb5dad-1069-46cd-b167-80b77016f03c-2_533_869_1160_244}

1. Use an appropriate algorithm to find the least weight (shortest) path from A to D.
2. Use Kruskal's algorithm to find a minimum spanning tree for the network.

5 A network is represented by the distance matrix below. For this network a direct connection between two vertices is always shorter than an indirect connection. \begin{enumerate}[label=(\alph*)] \item How does the distance matrix show that the arcs are undirected? The shortest distance from A to E is 180 . \item Write down the shortest route from A to E . \item Use Dijkstra's algorithm on the distance matrix to find the length of the shortest route from \(\mathbf { G }\) to each of the other vertices. The arcs represent roads and the weights represent distances in metres. The total length of all the roads is 1610 metres. Emily and Stephen have set up a company selling ice-creams from a van. \item Emily wants to deliver leaflets to the houses along each side of each road. Find the length of the shortest continuous route that Emily can use. \item Stephen wants to drive along each road in the ice-cream van.

1. Determine the length of the shortest route for Stephen if he starts at B.
2. Stephen wants to use the shortest possible route.