Dijkstra with vertex or edge exclusion

5 The arcs in the network below represent the tracks in a forest and the weights on the arcs represent distances in km. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_543_1269_392_438} Dijkstra's algorithm is to be used to find the shortest path from \(A\) to \(G\).

1. Apply Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). Show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Do not cross out your working values. Write down the route of the shortest path from \(A\) to \(G\) and give its length. The track joining \(B\) and \(D\) is washed away in a flood. It is replaced by a new track of unknown length, \(x \mathrm {~km}\). \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_544_1271_1480_438}
2. What is the smallest value that \(x\) can take so that the route found in part (i) is still a shortest path? If the value of \(x\) is smaller than this, what is the weight of the shortest path from \(A\) to \(G\) ?
3. (a) For what values of \(x\) will vertex \(E\) have two temporary labels? Write down the values of these temporary labels.
   (b) For what values of \(x\) will vertex \(C\) have two temporary labels? Write down the values of these temporary labels. Dijkstra's algorithm has quadratic order.
4. If a computer takes 20 seconds to apply Dijkstra's algorithm to a complete network with 50 vertices, approximately how long will it take for a complete network with 100 vertices?

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} Figure 4 shows a network of roads through eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc is the length of that road in km .

1. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
   (5) There is a fair in village C and you cannot drive through the village. A shortest route from A to H which avoids C needs to be found.
2. State this new minimal route and its length.
   (2)

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

1. Explain what is meant, in a network, by the term path.
   (2) Figure 4 represents a network of canals. The number on each arc represents the length, in miles, of the corresponding canal.
2. Use Dijkstra's algorithm to find the shortest path from S to T . State your path and its length.
3. Write down the length of the shortest path from S to F . Next week the canal represented by \(\operatorname { arc } \mathrm { AB }\) will be closed for dredging.
4. Find a shortest path from S to T avoiding AB and state its length.

5. \begin{figure}[h] \end{figure} Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.

1. Use Dijkstra's algorithm to find the shortest route from S to T . State your shortest route and its length.
   (6)
2. Explain how you determined your shortest route from your labelled diagram.
   (2) Due to flooding, the roads in and out of D are closed.
3. Find the shortest route from S to T avoiding D . State your shortest route and its length.
   (2)

4. \begin{figure}[h] \end{figure} Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn 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 the shortest path and its length. On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.
2. Use the route inspection algorithm to find the length of the shortest inspection route. State the edges that should be repeated. You should make your method and working clear.
   (5) The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A.
3. 1. State the edges that should be repeated.
   2. State a possible route and calculate its length. You must make your method and working clear.

7. \begin{figure}[h] \end{figure} Figure 5 shows the possible bus journeys linking towns, S, A, B, C, D, E, F, G, H and T. Each arc represents a bus journey. The number on each arc represents the cost, in pounds, of travelling along that route.

1. Use Dijkstra's algorithm, on the diagram in the answer book to find the cheapest route from S to T. State your cheapest route and its cost.
   (6)
2. Explain how you determined your cheapest route from your labelled diagram. The bus journey from S to B is cancelled due to a driver's illness.
3. Find the cheapest route from S to T that does not include SB , and state its cost.

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]

7 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows some of the main roads connecting Royton to London. The numbers on the edges represent the travelling times, in minutes, between adjacent towns. David lives in Royton and is planning to travel along some of the roads to a meeting in London. \includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-06_2196_1479_557_310}

1. 1. Use Dijkstra's algorithm on Figure 1 to find the minimum travelling time from Royton to London.
   2. Write down the route corresponding to this minimum travelling time.
2. On a particular day, before David leaves Royton, he knows that the road connecting Walsall and Marston is closed. Find the minimum extra time required to travel from Royton to London on this day. Write down the corresponding route.

3 The network below shows 11 towns, \(A , B , \ldots , K\). The number on each edge shows the time, in minutes, to travel between a pair of towns.

1. 1. Use Dijkstra's algorithm on the diagram below to find the minimum time to travel from \(A\) to \(K\).
   2. State the corresponding route.
2. On a particular day, Jenny travels from \(A\) to \(K\) but visits her friend at \(D\) on her way. Find Jenny's minimum travelling time.
3. On a different day, all roads connected to \(I\) are closed due to flooding. Jenny does not visit her friend at \(D\). Find her minimum time to travel from \(A\) to \(K\). State the route corresponding to this minimum time.
   [0pt] [2 marks] \section*{Answer space for question 3}
   \includegraphics[max width=\textwidth, alt={}]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-06_1478_1548_1213_239}

\includegraphics{figure_5} Figure 5 shows a network of roads. The number on each arc represents the length of that road in km.

1. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(J\). State your shortest route and its length. [5]
2. Explain how you determined the shortest route from your labelled diagram. [2]

The road from \(C\) to \(F\) will be closed next week for repairs.

1. Find the shortest route from \(A\) to \(J\) that does not include \(CF\) and state its length. [3]

(Total 10 marks)