Basic Dijkstra's algorithm application

6 The network opposite shows some roads connecting towns. The number on each edge represents the length, in miles, of the road connecting a pair of towns.

1. 1. Use Dijkstra's algorithm on the network to find the minimum distance from \(A\) to \(J\).
   2. Write down the corresponding route.
2. The road \(A J\) is a dual carriageway. Ken drives at 60 miles per hour on this road and drives at 50 miles per hour on all other roads. Find the minimum time to travel from \(A\) to \(J\).
   \includegraphics[max width=\textwidth, alt={}]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-15_2487_1714_221_152}

4 The network below shows some pathways at a school connecting different departments. The number on each edge represents the time taken, in minutes, to walk along that pathway. Carol, the headteacher, wishes to walk from her office ( \(O\) ) to the Drama department (D) .

1. 1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(O\) to \(D\).
   2. Write down the corresponding route.
2. On another occasion, Carol needs to go from her office to the Business Studies department \(( B )\).
   1. Write down her minimum walking time.
   2. Write down the route corresponding to this minimum time. \includegraphics[max width=\textwidth, alt={}, center]{3b7f04ff-e340-41ad-b50e-a02f94f02e8b-08_1499_1714_1208_153}

4 The edges on the network below represent some major roads in a city. The number on each edge is the minimum time taken, in minutes, to drive along that road.

1. 1. Use Dijkstra's algorithm on the network to find the shortest possible driving time from \(A\) to \(J\).
   2. Write down the corresponding route.
2. A new ring road is to be constructed connecting \(A\) to \(J\) directly. Find the maximum length of this new road from \(A\) to \(J\) if the time taken to drive along it, travelling at an average speed of \(90 \mathrm {~km} / \mathrm { h }\), is to be no more than the time found in part (a)(i). \section*{(a)(i)} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-08_912_1276_1053_429}

7 [Answer this question on the insert provided.]
The network below represents a simplified map of the centre of a small town. The arcs represent roads and the weights on the arcs represent distances, in units of 100 metres. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-06_725_1259_495_443}

1. 1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest route from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. State the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(J\), and give their lengths. [7]
   2. The shortest route from \(E\) to \(J\) that passes through every vertex can be treated as being made up of two parts, one from \(E\) to \(A\) and the other from \(A\) to \(J\). Use your answers to part (i) to write down the length of the shortest such route. List the vertices in the order that they are visited in travelling from \(E\) to \(J\) using this route.
   3. Explain why a similar approach to that used in parts (a)(i) and (a)(ii) would not give the shortest route between \(G\) and \(H\) that passes through every vertex.
2. By considering pairings of odd nodes, find the length of the shortest route that starts at \(A\) and ends at \(E\) and uses every arc at least once. \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
   4736
   Decision Mathematics 1
   INSERT for Questions 4 and 7
   Wednesday

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]

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 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.

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}

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 .

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.

6. \begin{figure}[h] \end{figure} Figure 5 shows a network of cycle tracks within a national park. The number on each arc represents the time taken, in minutes, to cycle along the corresponding track.

1. Use Dijkstra's algorithm to find the quickest route from S to T. State your quickest route and the time it takes.
   (6)
2. Explain how you determined your quickest route from your labelled diagram.
3. Write down the quickest route from E to T .

1. \begin{figure}[h] \end{figure} Figure 1 shows a network of roads between eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc gives the length, in miles, of the corresponding road.

1. Use Dijkstra's algorithm to find the shortest distance from A to H .
   (5)
2. State your shortest route.
   (1)
3. Write down the shortest route from H to C and state its length.
   (2)

7. \begin{figure}[h] \end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\). A route of minimum length is required. It is decided to use Dijkstra's algorithm to find the shortest routes between \(\mathrm { C } _ { 1 }\) and J and between \(\mathrm { C } _ { 2 }\) and J .

1. Explain why J , rather than \(\mathrm { C } _ { 1 }\) or \(\mathrm { C } _ { 2 }\), should be chosen as the starting vertex.
   (1)
2. Use Dijkstra's algorithm to find the shortest route needed to transport the crane. State your route and its length.
   (6)

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

1. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
   (6)
2. State the shortest distance from A to G .
   (1)

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-006_412_1561_568_233}

1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from \(A\) to \(J\).
   (6 marks)
2. State the corresponding route.
   (1 mark)

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-05_412_1561_568_233}

1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from \(A\) to \(J\).
   (6 marks)
2. State the corresponding route.
   (1 mark)

4 The network opposite shows roads connecting 10 villages, \(A , B , \ldots , J\). The time taken to drive along a road is not proportional to the length of the road. The number on each edge shows the average time, in minutes, to drive along each road.

1. A commuter wishes to drive from village \(A\) to the railway station at \(J\).
   1. Use Dijkstra's algorithm, on the diagram opposite, to find the shortest driving time from \(A\) to \(J\).
   2. State the corresponding route.
2. A taxi driver is in village \(D\) at 10.30 am when she receives a radio call asking her to pick up a passenger at village \(A\) and take him to the station at \(J\). Assuming that it takes her 3 minutes to load the passenger and his luggage, at what time should she expect to arrive at the station?
   [0pt] [2 marks]
   \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-09_2484_1717_223_150}

7 Let the new value of \(i\) be \(i + 1\).

1. Apply the sorting algorithm to the list of numbers shown below. Record in the table provided the state of the list after each pass. Record the number of comparisons and the number of swaps that you make in each pass. (The result of the first pass has already been recorded.) List: \(\begin{array} { l l l l l l } 9 & 11 & 7 & 3 & 13 & 5 \end{array}\)
2. Suppose now that the list is split into two sublists, \(\{ 9,11,7 \}\) and \(\{ 3,13,5 \}\). The sorting algorithm is adapted to apply to three numbers, and is applied to each sublist separately. This gives \(\{ 7,9,11 \}\) and \(\{ 3,5,13 \}\). How many comparisons and swaps does this need?
3. How many further swaps would the original algorithm need to sort the revised list \(\{ 7,9,11,3,5,13 \}\) into increasing order? 3 The network below represents a number of villages together with connecting roads. The numbers on the arcs represent distances (in miles). \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-3_684_785_1612_625}
4. Use Dijkstra's algorithm to find the shortest routes from A to each of the other villages. Give these shortest routes and the corresponding distances. Traffic in the area travels at 30 mph . An accident delays all traffic passing through C by 20 minutes.
5. Describe how the network can be adapted and used to find the fastest journey time from A to F .

\includegraphics{figure_1} Figure 1 shows a network of roads. Erica wishes to travel from \(A\) to \(L\) as quickly as possible. The number on each edge gives the time, in minutes, to travel along that road.

1. Use Dijkstra's algorithm to find a quickest route from \(A\) to \(L\). Complete all the boxes on the answer sheet and explain clearly how you determined the quickest route from your labelling. [7]
2. Show that there is another route which also takes the minimum time [1]

\includegraphics{figure_5} Figure 5 shows a network of cycle tracks within a national park. The number on each arc represents the time taken, in minutes, to cycle along the corresponding track.

1. Use Dijkstra's algorithm to find the quickest route from S to T. State your quickest route and the time it takes. [6]
2. Explain how you determined your quickest route from your labelled diagram. [2]
3. Write down the quickest route from E to T. [1]

(Total 9 marks)

Answer this question on the insert provided. Jenny needs to travel to London to arrive in time for a morning meeting. The graph below represents the various travel options that are available to her. \includegraphics{figure_3} It takes Jenny 120 minutes to drive from her home to the local airport and check in (arc \(JA\)). The journey from the local airport to Gatwick takes 80 minutes. From Gatwick to the underground station takes 60 minutes, and walking from the underground station to the meeting venue takes 15 minutes. Alternatively, Jenny could get a taxi from Gatwick to the meeting venue; this takes 80 minutes. It takes Jenny 15 minutes to drive from her house to the train station. Alternatively, she can walk to the bus stop, which takes 5 minutes, and then get a bus to the train station, taking another 20 minutes. From the train station to Paddington takes 300 minutes, and from Paddington to the underground station takes a further 20 minutes. Alternatively, Jenny could walk from Paddington to the meeting venue, taking 30 minutes. Jenny can catch a coach from her local bus stop to Victoria, taking 400 minutes. From Victoria she can either travel to the underground station, which takes 10 minutes, or she can walk to the meeting venue, which takes 15 minutes. The final option available to Jenny is to drive to a friend's house, taking 240 minutes, and then continue the journey into London by train. The journey from her friend's house to Waterloo takes Jenny 30 minutes. From here she can either go to the underground station, which takes 20 minutes, or walk to the meeting venue, which takes 40 minutes.

1. Weight the arcs on the graph in the insert to show these times. Apply Dijkstra's algorithm, starting from \(J\), to give a permanent label and order of becoming permanent at each vertex. Stop when you have assigned a permanent label to vertex \(M\). Write down the route of the shortest path from \(J\) to \(M\). [9]
2. What does the value of the permanent label at \(M\) represent? [1]
3. Give two reasons why Jenny might choose to use a different route from \(J\) to \(M\). [2]

This question should be answered on the sheet provided. \includegraphics{figure_1} Figure 1 above shows distances in miles between 10 cities. Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:

1. the order in which you labelled the vertices,
2. how you used your labelled diagram to find the shortest route. [10 marks]