Dijkstra combined with MST

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?

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.

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?

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.

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.