7.04a Shortest path: Dijkstra's algorithm

3 Whilst waiting for her meal to be served, Alice tries to construct a network to represent the meals offered in the restaurant. \includegraphics[max width=\textwidth, alt={}, center]{9bb2d545-3764-4930-a8a8-9dc5e25d0836-3_684_1310_365_379}

1. Use Dijkstra's algorithm to find the cheapest route through the undirected network from "start" to "end". Give the cost and describe the route. Use the lettering given on the network in your answer book.
2. Criticise the model and suggest how it might be improved.

5 The matrix shows the distances in miles between towns where direct routes exist.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to F . Give the route and its length.
3. Use Kruskal's algorithm to find a minimum connector for the network, showing your working. Draw your connector and give its total length.
4. How much shorter would AD have to be if it were to be included in
   (A) a shortest route from A to F ,
   (B) a minimum connector?

3 The network shows distances between vertices where direct connections exist. \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-3_518_691_1742_687}

1. Use Dijkstra's algorithm to find the shortest distance and route from A to F .
2. Explain why your solution to part (i) also provides the shortest distances and routes from A to each of the other vertices.
   [0pt]
3. Explain why your solution to part (i) also provides the shortest distance and route from B to F. [1]

4 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest paths from A to each of the other vertices. Give the paths and their lengths.
3. Draw a new network containing all of the edges in your shortest paths, and find the total length of the edges in this network.
4. Find a minimum connector for the original network, draw it, and give the total length of its edges.
5. Explain why the method defined by parts (i), (ii) and (iii) does not always give a minimum connector.

1 The weights on the arcs in the network represent times in minutes to travel between vertices. \includegraphics[max width=\textwidth, alt={}, center]{d1e0f047-6484-435b-a685-2cbbf81a6b02-2_606_782_402_628}

1. Use Dijkstra's algorithm to find the fastest route from A to F . Give the route and the time.
2. Use an algorithm to find the minimum connector for the network, showing your working. Find the minimum time to travel from A to F using only arcs in the minimum connector.

5 The table shows the weights on the arcs of a network.

1. Draw the network.
2. Apply Dijkstra's algorithm to find the least weight route from G to D. (Do this on the network you drew for part (i).) Give your route and its total weight.
3. Find by inspection the route from \(G\) to \(D\) such that the minimum of the weights for arcs on the route is as large as possible. Give your route and its minimum arc weight. Give an application in which this might be needed.
4. Consider how Dijkstra's algorithm could be modified to solve the problem in part (iii). Explain how to update working values. Explain how to select the next vertex to be permanently labelled.

6 The matrix gives the lengths of the arcs of a network.

1. Using the copy of the matrix in your answer book, apply the tabular form of Prim's algorithm to find a minimum connector for the network. Start by choosing vertex A and show the order in which you include vertices.
   List the arcs in your connector and give its total length. Serena takes a different approach to find a minimum connector. She first uses Dijkstra's algorithm to find shortest paths from A to each of the other vertices. She then uses the arcs in those paths to construct a connector.
2. Draw the network using the vertices printed in your answer book.
3. Apply Serena's method to produce a connector. List the arcs in the connector and give its total length. Serena adapts her method by starting from each vertex in turn, producing six connectors, from which she chooses the best.
4. Serena's approach will not find the minimum connector in all networks, but it is an algorithm. What is its algorithmic complexity? Justify your answer.

1

1. Use Dijkstra's algorithm to find the shortest distances and corresponding routes from A to each of the other vertices in the given network. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-2_588_792_632_632}
2. If the shortest distances and routes between every pair of vertices are required how many applications of Dijkstra will be needed?

6 The table shows the distances in miles, where direct rail connections are possible, between 11 cities in a country. The government is proposing to construct a high-speed rail network to connect the cities.

1. Use the tabular form of Prim's algorithm, starting at vertex P , to find a minimum connector for the network. Draw your minimum connector and give its total length.
2. Give one advantage and two disadvantages of constructing a rail network using only the arcs of a minimum connector.
3. Use Dijkstra's algorithm on the diagram in the Printed Answer Book, to find the shortest route and distance from P to Nr in the original network.
4. Give the shortest distance from P to Nr using only arcs in your minimum connector.

1 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to G . Give the route and its length.

4 The table defines a network on 6 nodes, the numbers representing distances between those nodes.

1. Use Dijkstra's algorithm to find the shortest routes from A to each of the other vertices. Give those routes and their lengths.
2. Jack wants to find a minimum spanning tree for the network.
   1. Apply Prim's algorithm to the network, draw the minimum spanning tree and give its length. Jill suggests the following algorithm is easier.
      Step 1 Remove an arc of longest length which does not disconnect the network
      Step 2 If there is an arc which can be removed without disconnecting the network then go to Step 1
      Step 3 Stop
   2. Show the order in which arcs are removed when Jill's algorithm is applied to the network.
   3. Explain why Jill's algorithm always produces a minimum spanning tree for a connected network.
   4. In a complete network on \(n\) vertices there are \(\frac { n ( n - 1 ) } { 2 }\) arcs. There are \(n - 1\) arcs to include when using Prim's algorithm. How many arcs are there to remove using Jill's algorithm? For what values of \(n\) does Jill have more arcs to remove than Prim has to include?

6 A mountain ridge separates two populated areas. Networks representing roads connecting the villages in each area are shown below. The numbers on the arcs represent distances in kilometres. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-7_524_1429_340_319} There is also a mountain road of length 15 kilometres connecting C to Z .

1. A national bus company needs a route from A to X .
   1. Use Dijkstra's algorithm on the complete network, including CZ, to find the shortest route from A to X . Give the route and its corresponding distance.
   2. Would it need fewer computations to use Dijkstra's algorithm on the network for villages A to F to find the shortest route from A to C, and then use Dijkstra's algorithm on the network for villages U to Z to find the shortest route from Z to X? Give a brief justification for your answer.
2. The local council needs to discover which roads it should keep clear of snow during the winter to keep all the villages connected, and the corresponding total length of road.
   1. Use Kruskal's algorithm on the network for villages A to F to find a minimum connector for \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } \}\). Show your use of the algorithm. Draw your minimum connector.
   2. Use Prim's algorithm on the network for villages U to Z to find a minimum connector for \(\{ \mathrm { U } , \mathrm { V } , \mathrm { W } , \mathrm { X } , \mathrm { Y } , \mathrm { Z } \}\), starting at U . Show your use of the algorithm. Draw your minimum connector.
   3. What is the total length of road that the council must keep clear of snow?

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 3 shows a weighted network. The number on each arc indicates the weight of that arc.

1. Use Dijkstra's algorithm to find a path of least weight from \(A\) to \(J\) and state the weight of the path. Your solution must show clearly how you have applied the algorithm including:
   1. the order in which the vertices were labelled,
   2. how you determined the path of least weight.
2. Find if there are any other paths of least weight and explain your answer.
3. Describe a practical problem that could be modelled by the above network.

3. \begin{figure}[h] \end{figure} Figure 1 shows a graph in which \(y \geq 0\).
Given that the graph is a weighted network,

1. find the range of values for the path of lowest weight from \(S\) to \(T\). Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
2. find the range of values for the maximum flow from \(S\) to \(T\).
3. Give an example of a practical problem which could be solved by using:
   1. the weighted network in part (a),
   2. the capacitated network in part (b).

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.

1. Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\). You must show clearly:
   1. the order in which you labelled the vertices,
   2. how you found a route of minimum length from your labelling. Each night a security guard walks along each of the paths in Figure 2 at least once.
2. The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
   (4 marks)

6 [Figures 4, 5, 6 and 7, printed on the insert, are provided for use in this question.]

1. The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity, in litres per minute, indicated on each edge. \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_350_878_532_591}
   1. Show that the value of the cut shown on the diagram is 97 .
   2. The cut shown on the diagram can be represented as \(\{ S , C \} , \{ A , B , T \}\). Complete the table on Figure 4, giving the value of each of the 8 possible cuts.
   3. State the value of the maximum flow through the network, giving a reason for your answer.
   4. Indicate on Figure 5 a possible flow along each edge corresponding to this maximum flow.
2. Extra pipes, \(B D , C D\) and \(D T\), are added to form a new system, with the capacity, in litres per minute, indicated on each edge of the network below. \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_483_977_1724_520}
   1. Taking your values from Figure 5 as the initial flow, use the labelling procedure on Figure 6 to find the new maximum flow through the network. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the new maximum flow, and, on Figure 7, indicate a possible flow along each edge corresponding to this maximum flow.

6 A retail company has warehouses at \(P , Q\) and \(R\), and goods are to be transported to retail outlets at \(Y\) and \(Z\). There are also retaining depots at \(U , V , W\) and \(X\). The possible routes with the capacities along each edge, in van loads per week, are shown in the following diagram. \includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-14_673_1193_577_429}

1. On Figure 5 opposite, add a super-source, \(S\), and a super-sink, \(T\), and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each edge that you have added.
2. On Figure 6, write down the maximum flows along the routes SPUYT and SRVWZT.
3. 1. On Figure 7, add the vertices \(S\) and \(T\) and the edges connecting \(S\) and \(T\) to the network. Using the maximum flows along the routes SPUYT and SRVWZT found in part (b) as the initial flow, indicate the potential increases and decreases of the flow on each edge of these routes.
   2. Use flow augmentation to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting routes on Figure 6 and modify the potential increases and decreases of the flow on Figure 7.
4. Find a cut with value equal to the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_629_1100_342_477}
   \end{figure} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 6}

   Route	Flow
   SPUYT
   SRVWZT

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 7} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_634_1109_1838_470}
   \end{figure}

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-14_807_1472_429_276}

1. Find the value of the cut \(Q\).
2. Figure 2 shows most of the values of a feasible flow of 34 litres per second from \(S\) to \(T\).
   1. Insert the missing values of the flows along \(D E\) and \(F G\) on Figure 2.
   2. Using this feasible flow as the initial flow, indicate potential increases and decreases of the flow along each edge on Figure 3.
   3. Use flow augmentation on Figure 3 to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
3. 1. State the value of the maximum flow.
   2. Illustrate your maximum flow on Figure 4.
4. Find a cut with capacity equal to that of the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_1646_1463_280_381}
   \end{figure} Figure 3 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_668_1230_1998_404}
   \end{figure}

8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge. \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-22_743_977_404_536}

1. Find the maximum flow along each of the routes \(A B E H , A C F H\) and \(A D G H\) and enter their values in the table on Figure 4 opposite.
2. 1. Taking your answers to part (a) as the initial flow, use the labelling procedure on Figure 4 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow and, on Figure 5 opposite, illustrate a possible flow along each edge corresponding to this maximum flow.
3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4}

   Route	Flow
   \(A B E H\)
   \(A C F H\)
   \(A D G H\)

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_746_972_397_845}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_739_971_1311_539}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-24_2253_1691_221_153}

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}

1. Find the value of the cut \(Q\).
2. Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(B T , D E\) and \(E T\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4 opposite.
   2. Use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 5 opposite.
4. Find a cut with value equal to that of the maximum flow. You may wish to show the cut on the network above. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
   \end{figure} Figure 4 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}

5 The network shows the evacuation routes along corridors in a college, from two teaching areas to the exit, in case of a fire alarm sounding. \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-14_729_1013_434_497} The two teaching areas are at \(A\) and \(G\) and the exit is at \(X\). The number on each edge represents the maximum number of people that can travel along a particular corridor in one minute.

1. Find the value of the cut shown on the diagram.
2. Find the maximum flow along each of the routes \(A B D X , G F B X\) and \(G H E X\) and enter their values in the table on Figure 3 opposite.
3. 1. Taking your answers to part (b) as the initial flow, use the labelling procedure on Figure 3 to find the maximum flow through the network. You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow, and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
4. During one particular fire drill, there is an obstruction allowing no more than 45 people per minute to pass through vertex \(B\). State the maximum number of people that can move through the network per minute during this fire drill. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_905_1559_331_292}
   \end{figure} Figure 4 \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_689_851_1370_598} Maximum flow is \(\_\_\_\_\) people per minute.

2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}

1. Write down the capacity of edge \(E F\).
2. State the source vertex.
3. State the sink vertex.
4. Find the values of \(x , y\) and \(z\).
5. Find the value of the initial flow.
6. Find the value of a cut through the edges \(E B , E C , E D , E F\) and \(E G\).

7 Figure 2 shows a network of pipes. Water from two reservoirs, \(R _ { 1 }\) and \(R _ { 2 }\), is used to supply three towns, \(T _ { 1 } , T _ { 2 }\) and \(T _ { 3 }\).
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.

1. Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
2. 1. Use the initial flow and the labelling procedure on Figure 3 to find the maximum flow through the network. You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}

6. The network in the figure above, shows the distances in km , along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A . By deleting D, a lower bound for the length of the route was found to be 586 km .
By deleting F, a lower bound for the length of the route was found to be 590 km .

1. By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer.
2. By inspection complete the table of least distances. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(8)
   (8)
   (Total 13 marks)} \includegraphics[alt={},max width=\textwidth]{a5d69a77-c196-483c-a550-1a55363555af-3_780_889_1069_1078}
   \end{figure} (4) The table can now be taken to represent a complete network. The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km .
   Starting at F, an upper bound for the length of the route was found to be 707 km .
3. Starting at C , use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the

   	A	B	C	D	E	F	G	H
   A	-	84	85	138	173		149	52
   B	84	-	130	77	126	213	222	136
   C	85	130	-	53	88	83	92
   D	138	77	53	-	49			190
   E	173	126	88	49	-	100	180	215
   F		213	83		100	-	163	115
   G	149	222	92		180	163	-	97
   H	52	136		190	215	115	97	-

   three, giving a reason for your answer.
   (4) (Total 13 marks)

1. \begin{figure}[h] \end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
   (3)
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
   (1)
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
   (2)