Dijkstra with route via intermediate vertex

5 The network below represents a single-track railway system. The vertices represent stations, the arcs represent railway tracks and the weights show distances in km. The total length of the arcs shown is 60 km . \includegraphics[max width=\textwidth, alt={}, center]{d783915d-5950-4a97-b6a0-70959214e218-5_442_1152_429_459}

1. Apply Dijkstra's algorithm to the network, starting at \(G\), to find the shortest distance (in km ) from \(G\) to \(N\) and write down the route of this shortest path. Greg wants to travel from the station represented by vertex \(G\) to the station represented by vertex \(N\). He especially wants to include the track \(K L\) (in either direction) in his journey.
2. Show how to use your working from part (i) to find the shortest journey that Greg can make that fulfils his requirements. Write down his route. Percy Li needs to check each track to see if any maintenance is required. He wants to start and end at the station represented by vertex \(G\) and travel in one continuous route that passes along each track at least once. The direction of travel along the tracks does not matter.
3. Apply the route inspection algorithm, showing your working, to find the minimum distance that Percy will need to travel. Write down those arcs that Percy will need to repeat. If he travels this minimum distance, how many times will Percy travel through the station represented by vertex \(L\) ?

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.

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.

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)

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 .

1. (a) Explain what is meant by the term 'path'.
   (2)

\begin{figure}[h] \end{figure} Figure 1 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Piatrice wishes to travel from A to J.
(b) Use Dijkstra's algorithm to find the shortest path Piatrice could take from A to J. State your path and its length.
(6) Piatrice needs to return from J to A via G.
(c) Find the shortest path Piatrice could take from J to A via G and state its length.

4. \begin{figure}[h] \end{figure} Figure 5 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Olivia 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 shortest route. On a particular day Olivia must include G in her route.
2. Find a route of minimal time from A to J that includes G , and state its length

4. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} The weighted network shown in Fig. 3 models the area in which Bill lives. Each vertex represents a town. The edges represent the roads between the towns. The weights are the lengths, in km , of the roads.

1. Use Dijkstra's algorithm to find the shortest route from Bill's home at \(S\) to \(T\). Complete all the boxes on the answer sheet and explain clearly how you determined the path of least weight from your labelling. Bill decides that on the way to \(T\) he must visit a shop in town \(E\).
2. Obtain his shortest route now, giving its length and explaining your method clearly.

4. \begin{figure}[h] \end{figure} Figure 3 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Liz wishes to travel from S to T .

1. Use Dijkstra's algorithm to find the shortest path from S to T . State your path and its length. On a particular day, Liz must include F in her route.
2. Find the shortest path from S to T that includes F , and state its length.

3. \begin{figure}[h] \end{figure} Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to traverse each road.

1. Use Dijkstra's algorithm to find the quickest route from S to T. State your quickest route and the time taken.
   (6) It is now necessary to include E in the route.
2. Determine the effect that this will have on the time taken for the journey. You must state your new quickest route and the time it takes.
   (3)

5. \begin{figure}[h] \end{figure} Sharon is planning a road trip from Preston to York. Figure 2 shows the network of roads that she could take on her trip. The number on each arc is the length of the corresponding road in miles.

1. Use Dijkstra's algorithm to find the shortest route from Preston (P) to York (Y). State the shortest route and its length.
   (6) Sharon has a friend, John, who lives in Manchester (M). Sharon decides to travel from Preston to York via Manchester so she can visit John. She wishes to minimise the length of her route.
2. State the new shortest route. Hence calculate the additional distance she must travel to visit John on this trip. You must make clear the numbers you use in your calculation.
   (3)

3. \begin{figure}[h] \end{figure} Figure 3 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 J. State the shortest route and its length.
2. Explain how you determined the shortest route from your labelled diagram.
3. Find the shortest route from A to J via E and state its length.

4. \begin{figure}[h] \end{figure} Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to F . State your path and its length. On another day, Sarah wishes to travel from A to F via J.
2. Find a route of minimal length that goes from A to F via J and state its length.
3. Use Prim's algorithm, starting at G , to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
4. State the length, in miles, of the minimum spanning tree.

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

1. Use Dijkstra's algorithm to find the shortest route from \(S\) to \(T\) in Fig. 3. Show all necessary working in the boxes in the answer booklet. State your shortest route and its length.
2. Explain how you determined the shortest route from your labelling.
3. It is now necessary to go from \(S\) to \(T\) via \(H\). Obtain the shortest route and its length.

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.

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

1. Use Dijkstra's algorithm to find the shortest time to travel from \(S\) to \(T\). [4]
2. Find a route for Avinash to travel from \(S\) to \(T\) in the shortest time. State, with a reason, whether this route is a unique solution. [2]

On a particular day Avinash must include \(C\) in his route.

1. Find a route of minimal time from \(S\) to \(T\) that includes \(C\), and state its time. [2]

1. Explain what is meant by the term 'path'. [2]

\includegraphics{figure_3} Figure 3 shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Mary wishes to cycle from A to I as part of a cycling holiday. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to I. Show all necessary working in the boxes in Diagram 1 in the answer book. State your shortest path and its length. [6]
2. Explain how you determined the shortest path from your labelling. [2]

Mary wants to visit a theme park at E.

1. Find a path of minimal length that goes from A to I via E and state its length. [2]