7.04a Shortest path: Dijkstra's algorithm

3. \begin{figure}[h] \end{figure} Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track.
Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel. Given that Dijkstra's algorithm is to be applied only once to find Dyfan's route,

1. explain why the algorithm should begin at C.
2. Use Dijkstra's algorithm to find the shortest route from A to J via C. State this route and its length.
3. Use Prim's algorithm, starting at C , to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
4. State the total length, in km , of the minimum spanning tree.

3. \begin{figure}[h] \end{figure} [The total weight of the network is \(139 + x + y\) ]

1. Explain what is meant by the term "tree". Figure 3 represents a network of walkways in a warehouse.
   The arcs represent the walkways and the nodes represent junctions between them.
   The number on each arc represents the length, in metres, of the corresponding walkway.
   The values \(x\) and \(y\) are unknown, however it is known that \(x\) and \(y\) are integers and that $$9 < x < y < 14$$
2. 1. Use Dijkstra's algorithm to find the shortest route from A to M.
   2. State an expression for the length of the shortest route from A to M . The warehouse manager wants to check that all of the walkways are in good condition.
      Their inspection route starts at B and finishes at C .
      The inspection route must traverse each walkway at least once and be as short as possible.
3. State the arcs that are traversed twice.
4. State the number of times that H appears in the inspection route. The warehouse manager finds that the total length of the inspection route is 172 metres.
5. Determine the value of \(x\) and the value of \(y\)

1. \begin{figure}[h] \end{figure} [The total weight of the network is 189]
Figure 1 represents a network of pipes in a building. The number on each arc is the length, in metres, of the corresponding pipe.

1. Use Dijkstra's algorithm to find the shortest path from A to F . State the path and its length. On a particular day, Gabriel needs to check each pipe. A route of minimum length, which traverses each pipe at least once and which starts and finishes at A, needs to be found.
2. Use an appropriate algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
3. State the minimum length of Gabriel's route. A new pipe, BG, is added to the network. A route of minimum length that traverses each pipe, including BG, needs to be found. The route must start and finish at A. Gabriel works out that the addition of the new pipe increases the length of the route by twice the length of BG .
4. Calculate the length of BG. You must show your working.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.

1. Use Dijkstra's algorithm to find the shortest path from A to D, stating the path and its length. On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G .
2. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Find the length of Naasir's route. On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B .
4. 1. Determine the possible starting and finishing points so that the length of Naasir's route is minimised. You must give reasons for your answer.
   2. Find the length of Naasir's new route.

3. \begin{figure}[h] \end{figure} The network in Figure 2 shows the direct roads linking five villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E .
The number on each arc represents the length, in miles, of the corresponding road.
The roads from A to E and from C to B are one-way, as indicated by the arrows.

1. Complete the initial distance and route tables for the network provided in the answer book.
   (2)
2. Perform the first three iterations of Floyd's algorithm. You should show the distance table and the route table after each of the three iterations. After five iterations of Floyd's algorithm the final distance table and partially completed final route table are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Distance table}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	12	7	6	3
   B	15	-	22	21	18
   C	7	5	-	4	7
   D	11	9	4	-	3
   E	14	12	7	3	-

   \end{table} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Route table}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	A
   B	A	B
   C	A	B	C
   D	C	C	C	D
   E	D	D	D	D	E

   \end{table}
3. 1. Explain how the partially completed final route table can be used to find the shortest route from E to A.
   2. State this route. Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table.
4. 1. State the cycle obtained using the nearest neighbour algorithm.
   2. State the length of this cycle.
   3. Interpret the cycle in terms of the actual villages visited.
   4. Prove that Mabintou's cycle is not optimal.

3. \begin{figure}[h] \end{figure} Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.

1. Set up initial time and route matrices. The matrices after two iterations of Floyd's algorithm are shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	8	4	7	18
   B	8	-	3	15	10
   C	4	3	-	11	6
   D	7	15	1	-	1
   E	18	10	6	1	-

   \end{table} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Route matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	A	B	C	D	B
   B	A	B	C	A	E
   C	A	B	C	A	E
   D	A	A	C	D	E
   E	B	B	C	D	E

   \end{table}
2. Perform the next two iterations of Floyd's algorithm that follow from the tables above. You should show the time and route matrices after each iteration. The final time matrix after completion of Floyd's algorithm is shown below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Final time matrix}

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	A	B	C	D	E
   A	-	7	4	7	8
   B	7	-	3	10	9
   C	4	3	-	7	6
   D	5	4	1	-	1
   E	6	5	2	1	-

   \end{table}
3. 1. Use the nearest neighbour algorithm, starting at A , to find a Hamiltonian cycle in the complete network of shortest times.
   2. Find the time taken for this cycle.
   3. Interpret the cycle in terms of the actual villages visited.

4. \begin{figure}[h] \end{figure} Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the six cities.
An initial route matrix is given in the answer book.

1. Set up the initial time matrix.
2. Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration. The final time matrix after completion of Floyd's algorithm is shown below.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	A	B	C	D	E	F
   A	-	57	95	147	63	220
   B	57	-	72	204	120	197
   C	95	72	-	242	158	125
   D	147	204	242	-	84	275
   E	63	120	158	84	-	191
   F	220	197	125	275	191	-

   A route is needed that minimises the total time taken to traverse each road at least once.
   The route must start at B and finish at E .
3. Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
4. Write down the length of the route.

6. \begin{figure}[h] \end{figure} In Figure 4 the weights on the arcs represent distances.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to H .
   2. State the length of the shortest path from A to H . One application of Dijkstra's algorithm has order \(n ^ { 2 }\), where \(n\) is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra's algorithm from each node of the network. It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.
2. Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.
3. Explain why your answer to part (b) can only be an approximation.

2. \begin{figure}[h] \end{figure} [The total weight of the network is 299] Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track. One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to K .
   2. State the length of the shortest path from A to K .
      (6) The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E .
2. 1. State the edges that will need to be traversed twice.
   2. Find the length of Blanche's route. It is now decided to start the inspection route at A and finish at K . Blanche must minimise the length of her route and travel along each track at least once.
3. By considering the pairings of all relevant nodes, find the length of Blanche's new route. You must make your method and working clear.

3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one-way only. \begin{table}[h] \end{table}

1. By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. Floyd's algorithm is to be used to find the complete network of shortest distances between the six classrooms. The distance matrix after two iterations of Floyd's algorithm is shown in Table 2. \begin{table}[h]

   	A	B	C	D	E	F
   A	-	12	29	20	29	11
   B	12	-	17	8	41	23
   C	29	17	-	4	12	40
   D	24	36	4	-	53	13
   E	\(\infty\)	\(\infty\)	12	18	-	12
   F	11	23	40	13	12	-

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Perform the next two iterations of Floyd's algorithm that follow from Table 2. You should show the distance matrix after each iteration. The final distance matrix after completion of Floyd's algorithm is shown in Table 3.

   	A	B	C	D	E	F
   A	-	12	24	20	23	11
   B	12	-	12	8	24	21
   C	28	17	-	4	12	17
   D	24	21	4	-	16	13
   E	23	29	12	16	-	12
   F	11	23	17	13	12	-

   \section*{Table 3} Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.
3. 1. Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.
   2. Find the length of each of the two cycles.
   3. State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka's route.

1. \begin{figure}[h] \end{figure} Figure 1 shows the graph G.

1. State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
2. Write down an example of a Hamiltonian cycle on G.
3. State whether or not G is planar, justifying your answer.
4. State the number of arcs that would need to be added to G to make the graph \(\mathrm { K } _ { 5 }\) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-03_467_716_178_671} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.
5. For the network represented in Figure 2, complete the initial time matrix in the answer book. The time matrix after four iterations of Floyd's algorithm is shown in Table 1. \begin{table}[h]

   	A	B	C	D	E
   A	-	10	13	15	5
   B	10	-	3	5	4
   C	13	3	-	2	7
   D	15	5	2	-	7
   E	5	4	7	7	-

   \captionsetup{labelformat=empty} \caption{Table 1}
   \end{table}
6. Perform the final iteration of Floyd's algorithm that follows from Table 1, showing the time matrix for this iteration.

3. \begin{figure}[h] \end{figure} Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J.
The number on each edge gives the length of the corresponding edge.

1. 1. Use Dijkstra's algorithm to find the shortest path from A to J.
   2. State the length of the shortest path from A to J . One application of Dijkstra's algorithm has order \(n ^ { 2 }\), where \(n\) is the number of nodes in the network. It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.
2. Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 413] Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.

1. Use Dijkstra's algorithm to find the shortest path from A to J. Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track.
2. By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must
   The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route.
3. Determine which route, Abi's or Tarig's, is shorter. You must make your working clear.

4. \begin{figure}[h] \end{figure} The network in Figure 3 shows the roads linking a depot, D, and three collection points \(\mathrm { A } , \mathrm { B }\) and C . The number on each arc represents the length, in miles, of the corresponding road. The road from B to D is a one-way road, as indicated by the arrow.

1. Explain clearly if Dijkstra's algorithm can be used to find a route from D to A . The initial distance and route tables for the network are given in the answer book.
2. Use Floyd's algorithm to find a table of least distances. You should show both the distance table and the route table after each iteration.
3. Explain how the final route table can be used to find the shortest route from D to B . State this route. There are items to collect at \(\mathrm { A } , \mathrm { B }\) and C . A van will leave D to make these collections in any order and then return to D. A minimum route is required. Using the final distance table and the Nearest Neighbour algorithm starting at D,
4. find a minimum route and state its length. Floyd's algorithm and Dijkstra's algorithm are applied to a network. Each will find the shortest distance between vertices of the network.
5. Describe how the results of these algorithms differ.

3. \begin{figure}[h] \end{figure} In Figure 1 the weight of \(\operatorname { arc } \mathrm { SB }\) is denoted by \(x\) where \(x \geqslant 0\)

1. Explain why Dijkstra's algorithm cannot be used on the directed network in Figure 1.
   (1) It is given that the minimum weight route from S to T passes through B .
2. Use dynamic programming to find
   1. the range of possible values of \(x\)
   2. the minimum weight route from S to T .
      (12)

2 Answer this question on the insert provided. This diagram shows part of a network. There are other arcs connecting \(D\) and \(E\) to other parts of the network. Apply Dijkstra's algorithm starting from \(A\), as far as you are able, showing your working. Note: you will not be able to give permanent labels to all the vertices shown.

5 Answer part (i) of this question on the insert provided. Rhoda Raygh enjoys driving but gets extremely irritated by speed cameras.
The network represents a simplified map on which the arcs represent roads and the weights on the arcs represent the numbers of speed cameras on the roads. The sum of the weights on the arcs is 72 . \includegraphics[max width=\textwidth, alt={}, center]{8a1232ae-6a6e-4afb-8757-fffe4fc9570f-05_874_1484_664_333}

1. Rhoda lives at Ayton ( \(A\) ) and works at Kayton ( \(K\) ). Use Dijkstra's algorithm on the diagram in the insert to find the route from \(A\) to \(K\) that involves the least number of speed cameras and state the number of speed cameras on this route.
2. In her job Rhoda has to drive along each of the roads represented on the network to check for overhanging trees. This requires finding a route that covers every arc at least once, starting and ending at Kayton (K). Showing all your working, find a suitable route for Rhoda that involves the least number of speed cameras and state the number of speed cameras on this route.
3. If Rhoda checks the roads for overhanging trees on her way home, she will instead need a route that covers every arc at least once, starting at Kayton and ending at Ayton. Calculate the least number of speed cameras on such a route, explaining your reasoning.

3 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}

1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(E\), and all the arcs joined to \(E\), removed. Hence find a lower bound for the travelling salesperson problem on the original network.
3. Show that the nearest neighbour method, starting from vertex \(A\), fails on the original network.
4. Apply the nearest neighbour method, starting from vertex \(B\), to find an upper bound for the travelling salesperson problem on the original network.
5. Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from \(A\) to \(G\). State the weight of the path and give its route.
6. The sum of the weights of all the arcs is 300 . Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. The weights of least weight paths from vertex \(A\) should be found using your answer to part (v); the weights of other such paths should be determined by inspection.

1 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{e1495f6b-c09f-46a1-a6f8-02354e28887a-02_533_1353_342_395}

1. Apply Dijkstra's algorithm to the copy of this network in the insert to find the least weight path from \(A\) to \(F\). State the route of the path and give its weight.
2. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. Write down a closed route that has this least weight. An extra arc is added, joining \(B\) to \(E\), with weight 2 .
3. Write down the new least weight path from \(A\) to \(F\). Explain why the new least weight closed route, that uses every arc at least once, has no repeated arcs.

5 Answer this question on the insert provided. The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres. The sum of the weights on the arcs is 765 metres. \includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}

1. Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.
2. In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors. The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.
3. On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?

2 Answer this question on the insert provided.

1. Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
   \end{figure}
2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

2 Answer this question on the insert provided.

1. Use Dijkstra's algorithm to find the least weight route from \(A\) to \(G\) in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_458_584_525_760} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
   \end{figure}
2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_421_533_1307_779} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

4 Answer parts (i) and (ii) on the insert provided. Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown. \begin{figure}[h] \end{figure}

1. Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]
2. Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector. A bridge is built giving a direct road between P and Q of length 12 km .
3. What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)
4. What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)
5. Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once. Give this town and justify your answer.

1 Answer this question on the insert provided. \begin{figure}[h] \end{figure}

1. Apply Dijkstra's algorithm to the copy of Fig. 1 in the insert to find the least weight route from A to D. Give your route and its weight.
2. Arc DE is now deleted. Write down the weight of the new least weight route from A to D , and explain how your working in part (i) shows that it is the least weight.
   [0pt] [2]