7.04a Shortest path: Dijkstra's algorithm

7 A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.
The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.

1. Model this information as a network.
2. Use an appropriate algorithm to calculate the minimum distance from A to each of the other vertices. The run-time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with \(n\) vertices, the worst case is when the algorithm is applied to a network based on the complete graph \(\mathrm { K } _ { n }\). In each pass
   • A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.
   • The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are \(k\) such vertices this involves \(k - 1\) comparisons.
   • By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete graph \(\mathrm { K } _ { 4 }\).
   You are given that the total number of comparisons used when the algorithm is applied to a network based on \(\mathrm { K } _ { n }\) is \(( n - 1 ) ( n - 2 )\). A computer takes 0.03 seconds to apply this algorithm on a network based on \(\mathrm { K } _ { 7 }\).
3. Calculate, to \(\mathbf { 1 }\) decimal place, how many seconds it will take the computer to apply the algorithm to a network based on \(\mathrm { K } _ { 70 }\). \section*{Question 7 continues on the next page} The manager wants to construct a tour (a closed route) that passes each camera.
4. 1. Find a lower bound for the length of this tour by initially deleting D .
   2. Find an upper bound for the length of this tour by using the nearest neighbour algorithm starting from D.
   3. Deduce the length of the shortest possible tour. Briefly explain your reasoning. \section*{END OF QUESTION PAPER}

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

1. Use Dijkstra's algorithm to find the shortest path from A to J . State your path and its length. On a particular day Kim needs to check each pipe. A route of minimum length, which traverses each pipe at least once and starts and finishes at A, needs to be found.
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. Write down a possible route, giving its length. All the pipes directly attached to B are removed. Kim needs to check all the remaining pipes and may now start at any vertex and finish at any vertex. A route is required that excludes all those pipes directly attached to B .
4. State all possible combinations of starting and finishing points so that the length of Kim's route is minimised. State the length of Kim's route.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 196]
Figure 3 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Oliver wishes to travel by road from A to K as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to K . State the quickest route.
   (6) On a particular day Oliver must travel from B to K via A.
2. Find a route of minimal time from B to K that includes A , and state its length.
   (2) Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.
3. Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear.

6. \begin{figure}[h] \end{figure} Figure 4 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Stieg wishes to minimise the time spent driving from his home at A , to his office at H . The amount of traffic on two of the roads leading into H varies each day, and so the length of time taken to drive along these roads is expressed in terms of \(x\), where \(x > 7\)

1. Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H . State the length of each route, leaving your answer in terms of \(x\) where necessary.
   (7) On a particular day, the quickest route from A to H via G is 2 minutes quicker than the quickest route from A to H via E .
2. Calculate the value of \(x\). You must make your method and working clear.

3. \begin{figure}[h] \end{figure} Figure 4 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Sally wishes to travel from A to J. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to J. State the path and its length.
2. Find a route of minimal length that goes from D to H via A and state its length.
3. Use Prim's algorithm, starting at E , 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. Find the length, in kilometres, of your minimum spanning tree.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads. The number on each arc is the length, in km , of the corresponding road.

1. Use Dijkstra's algorithm to find the shortest route from A to L. State the shortest route and its length.
2. Explain how you determined the shortest route from your labelled diagram.
3. Find the length of the shortest route from J to F via A , and state your route.

6. \begin{figure}[h] \end{figure} [The total weight of the network is 269] Figure 3 models a network of roads. The number on each edge gives the time taken, in minutes, to travel along the corresponding road.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. Alan needs to travel along all the roads to check that they are in good repair. He wishes to complete his route as quickly as possible and will start at his home, H, and finish at his workplace, D.
2. By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in Alan's inspection route from H to D. You must make your method and working clear. For Alan's inspection route from H to D
3. 1. state the number of times vertex C will appear,
   2. state the number of times vertex D will appear.
4. Determine whether it would be quicker for Alan to start and finish his inspection route at H , instead of starting at H and finishing at D . You must explain your reasoning and show all your working.

5. \begin{figure}[h] \end{figure} [The total weight of the network is 253] Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road. One day, Mabintou wishes to travel from A to H. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to H . State your path and its length. On another day, Mabintou wishes to travel from F to K via A.
2. Find a route of minimum length from F to K via A and state its length. The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.
3. By considering the pairings of all relevant nodes, find the length of James' route. State the arcs that will need to be traversed twice. You must make your method and working clear.
   (6)
4. State the number of times that James will pass through F. It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.
5. State the vertex where the new inspection route will finish.
6. Calculate the difference between the lengths of the two inspection routes.

6. \section*{Question 6 continued} (b) \(\_\_\_\_\) (c) \section*{Question 6 continued}

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Shortest path from A to J: \(\_\_\_\_\) Length of shortest path from A to J: \(\_\_\_\_\) \section*{Question 2 continued} \begin{figure}[h] \end{figure} [The total weight of the network is 193] \section*{Question 2 continued} \section*{Question 2 continued}

3. \begin{figure}[h] \end{figure} [The total weight of the network is 458] Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.

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 . The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
2. By considering the pairings of all relevant nodes, find the length of Claude's route. State the arcs that will need to be traversed twice. If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
3. Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.

3. \begin{figure}[h] \end{figure} Figure 3 shows a network representing the time taken, in minutes, to travel by train between nine towns, A, B, C, D, E, F, G, H and T. A train is to travel from A to T without stopping.

1. Use Dijkstra's algorithm to find the quickest route from A to T and the time taken.
   (6) At present, the train travels from A to T via F without stopping.
2. Use your answer to (a) to find the quickest route from A to T via F and the time taken.
   (2) A train is to travel from A to T , stopping for 2 minutes at each town it passes through on its route.
3. Explain how you would adapt the network so that you could use Dijkstra's algorithm to find the quickest route for this train. You do not need to find this route.
   (2)

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

1. Use Dijkstra's algorithm to find the shortest distance from S to G . State the shortest route.
2. State both the shortest distance and the shortest route from S to H .

5. \begin{figure}[h] \end{figure}

1. Explain what is meant by the term 'path'.
   (2) Figure 4 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Tomek wishes to travel from A to J.
2. Use Dijkstra's algorithm to find the shortest path from A to J. State your path and its length.
   (6) On a particular day, Tomek needs to travel from G to J via A.
3. Find the shortest route from G to J via A , and find its length.
   (3) The road HJ becomes damaged and cannot be used. Tomek needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route he uses must start and finish at B .
4. Use an appropriate algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
   (5)
5. Write down a possible shortest inspection route.
   (1)

6. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 223]} Figure 4 models a network of roads. The number on each arc represents the length, in km , of the corresponding road. Pamela wishes to travel from A to B.

1. Use Dijkstra's algorithm to find the shortest path from A to B. State your path and its length. On a particular day, Pamela must include C in her route.
2. Find the shortest route from A to B that includes C , and state its length.
   (2) Due to damage, the three roads in and out of C are closed and cannot be used. Faith needs to travel along all the remaining roads to check that there is no damage to any of them. She must travel along each of the remaining roads at least once and the length of her inspection route must be minimised. Faith will start and finish at A .
3. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, and calculate its length. You must make your calculation clear. Faith now decides to start at vertex B and finish her inspection route at a different vertex. A route of minimum length that includes each road, excluding those directly connected to C , needs to be found.
5. State the finishing vertex of Faith's route. Calculate the difference between the length of this new route and the route found in (d).

4. \begin{figure}[h] \end{figure} [The total weight of the network is 275]
Figure 5 models a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each edge gives the time, in minutes, to travel along the corresponding road. Mandeep wishes to travel from A to J as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route. On Monday, Mandeep must travel from D to H via A.
2. Find the shortest time needed to travel from D to H via A . State the quickest route. On Wednesday, Mandeep needs to travel along each road to check that it is in good repair. She wishes to minimise the total time required to traverse the network. Mandeep plans to start and finish her inspection route at G.
3. Use an appropriate algorithm to find the roads that need to be traversed twice. You must make your method and working clear.
4. Write down a possible route, giving its duration. On Friday, all the roads leading directly to B are closed. Mandeep needs to check all the remaining roads and may start at any village and finish at any village. A route is required that excludes all those roads leading directly to B .
5. State all possible combinations of starting and finishing points so that the duration of Mandeep's route is minimised. Calculate the duration of Mandeep's minimum route.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads between ten villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.

1. Use Dijkstra's algorithm to find the shortest route from A to J. State the route and its length. During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.
2. Use Prim's algorithm, starting at A , to find a minimum connector for the five villages \(\mathrm { A } , \mathrm { B }\), C, D and E. You must clearly state the order in which you select the edges of your minimum connector.
3. Use Kruskal's algorithm to find a minimum connector for the five villages \(\mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.
4. Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.

6. 2. \begin{figure}[h] \end{figure} Shortest route: \(\_\_\_\_\) Length of shortest route: \(\_\_\_\_\) \begin{figure}[h] \end{figure} 3. \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\) \(\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}\) \begin{figure}[h] \end{figure} 4. \includegraphics[max width=\textwidth, alt={}, center]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-20_572_1454_1021_248} \section*{Key:} \section*{Diagram 1} 5. \section*{Diagram 1} 6.

7. \begin{figure}[h] \end{figure} [The total weight of the network is \(205 + 3 x\) ] Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Malcolm wishes to minimise the time spent driving from his home at A to his office at H . The delays from roadworks on two of the roads leading in to H vary daily, and so the time taken to drive along these roads is expressed in terms of \(x\), where \(x\) is fixed for any given day and \(x > 0\)

1. Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H. State the length of each route, leaving your answer in terms of \(x\) where necessary. On Monday, Malcolm needs to check each road. He must travel along each road at least once. He must start and finish at H and minimise the total time taken for his inspection route. Malcolm finds that his minimum duration inspection route requires him to traverse exactly four roads twice and the total time it takes to complete his inspection route is 307 minutes.
2. Calculate the minimum time taken for Malcolm to travel from A to H on Monday. You must make your method and working clear.

5. \begin{figure}[h] \end{figure} Figure 4 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Tamasi, who lives at A, needs to collect a caravan. Tamasi can collect a caravan from either J or K. Tamasi decides to use Dijkstra's algorithm once to find the shortest routes between A and J and between A and K.

1. State, with a reason, which vertex should be chosen as the starting vertex for the algorithm.
2. Use Dijkstra's algorithm to find the shortest routes from A to J and from A to K . You should state the routes and their corresponding lengths. Tamasi's brother lives at F . He needs to visit Tamasi at A and then visit their mother who lives at H .
3. Find a route of minimal length that goes from F to H via A .

17
25
31
15
11
46
17
27
-
15
47
E
32
F
35
G
-
} &
\hline & & & & & & & &
\hline 6.

6. \begin{figure}[h] \end{figure} [The total weight of the network is \(383 + x\) ]
Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\), H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible. The time taken to travel between towns G and J is unknown and is denoted by \(x\) minutes. Dijkstra's algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 in the answer book the "Order of labelling" and "Final value" at A and J, and the "Working values" at J , have already been completed.

1. Use Dijkstra's algorithm to find the fastest time to travel from A to H . State the quickest route. Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A . It is given that his route will take at least 440 minutes.
2. Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of \(x\).
3. Write down a possible route for Ezra. A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A . It is given that this inspection route takes exactly 488 minutes.
4. Determine the value of \(x\). You must give reasons for your answer.

6. \begin{figure}[h] \end{figure} [The total weight of the network is 315]
Figure 3 represents a network of roads between nine parks, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in miles, of the corresponding road.

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 . The roads between the parks need to be inspected. Robin must travel along each road at least once. Robin wishes to minimise the length of the inspection route. Robin will start the inspection route at C and finish at E .
2. By considering the pairings of all relevant nodes, find the length of Robin's route.
3. State the number of times Robin will pass through G . It is now decided to start and finish the inspection route at A. Robin must still minimise the length of the route and travel along each road at least once.
4. Calculate the difference between the lengths of the two inspection routes.
5. State the edges that need to be traversed twice in the route that starts and finishes at A , but do not need to be traversed twice in the route that starts at C and finishes at E .

3. \begin{figure}[h] \end{figure} Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger wishes to travel from A to J as quickly as possible.

1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route.
   (6)
2. Hence determine the weight of the minimum spanning tree for the network given in Figure 2. Give a reason for your answer. You do not need to find the minimum spanning tree.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 494]
Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3. The number on each arc represents the lengths, in kilometres, of the corresponding road.
The table below shows the shortest distances, in kilometres, between the nine factories. \section*{Table of shortest distances}

1. Starting at A, use Prim's algorithm to find a minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.
   (3)
2. State the weight of the minimum spanning tree.
   (1) A route is needed that minimises the total distance to traverse each road at least once. The route must start at E and finish at F .
3. Determine the length of this route. You must give a reason for your answer. It is now decided to start the route at C and finish the route at A . The route must include every road at least once and must still minimise the total distance travelled.
4. By considering the pairings of all relevant nodes, find the roads that need to be traversed twice. Naoko needs to visit all nine factories, starting and finishing at the same factory, and wishes to minimise the total distance travelled.
5. Starting at B, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Naoko's route. Write down the cycle, obtained from the table of shortest distances, which gives this upper bound.
6. By deleting C and all of its arcs, use the values in the table of shortest distances to find a lower bound for the length of Naoko's route.