Shortest Path

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.

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 .

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.

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.

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]

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\) ?

\includegraphics{figure_3} Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.

1. Use Dijkstra's algorithm to find the shortest distance from \(A\) to \(H\). [5]
2. Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at \(A\), and find its length. [The total weight of the network is 1241] [6]

\includegraphics{figure_3}

1. Apply Dijkstra's algorithm to the copy of this network in the answer booklet to find the least weight path from A to F. State the route of the path and give its weight. [6]

In the remainder of this question, any least weight paths required may be found without using a formal algorithm.

1. Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. [3]
2. Find the weight of the least weight route that uses every arc at least once, starting at A and ending at F. Explain how you reached your answer. [4]

4 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-3_918_1242_351_443} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the lengths of roads in kilometres.

1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest path 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. Find the route of the shortest path from \(A\) to \(G\). The total weight of the arcs is 120 kilometres.
2. By using an appropriate algorithm, find the length of a shortest route that uses every road starting and ending at \(A\). You should explain your method.
3. Find the length of a shortest route that uses every road starting at \(A\) and ending at \(G\). You should explain your method.

\(\mathbf { 4 }\) & 11 & 11 & 7 & 14 & 14
\hline

3 Floyd's algorithm is applied to the following network: \includegraphics[max width=\textwidth, alt={}, center]{483a681e-011a-464f-b7cb-007d894d1516-3_398_394_331_833} At the end of the third iteration of the algorithm the distance and route matrices are as follows:

Draw the complete network of shortest distances.
(ii) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
(iii) By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
(b) Solve the route inspection problem in the original network, and say how you can be sure that your solution is optimal. 4 A factory's output includes three products. To manufacture a tonne of product \(\mathrm { A } , 3\) tonnes of water are needed. Product B needs 2 tonnes of water per tonne produced, and product C needs 5 tonnes of water per tonne produced. Product A uses 5 hours of labour per tonne produced, product B uses 6 hours and product C uses 2 hours. There are 60 tonnes of water and 50 hours of labour available for tomorrow's production.
(i) Formulate a linear programming problem to maximise production within the given constraints.
(ii) Use the simplex algorithm to solve your LP, pivoting first on your column relating to product C.
(iii) An extra constraint is imposed by a contract to supply at least 8 tonnes of A . Use either two stage simplex or the big M method to solve this revised problem.

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]

\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)

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?

3 The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. Distance Matrix

3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times. \includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \end{table}

3 The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. Distance Matrix

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.

1. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(I\). Show all necessary working in the boxes in the answer booklet and state your shortest route and its length.
   (5) The park warden wishes to check each of the paths to check for frost damage. She has to cycle along each path at least once, starting and finishing at \(A\).
2. 1. Use an appropriate algorithm to find which paths will be covered twice and state these paths.
   2. Find a route of minimum length.
   3. Find the total length of this shortest route.
      (5)

The network below shows some paths on an estate. The number on each edge represents the time taken, in minutes, to walk along a path.

1. 1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(A\) to \(J\). [6]
   2. Write down the corresponding route. [1]
2. A new subway is constructed connecting \(C\) to \(G\) directly. The time taken to walk along this subway is \(x\) minutes. The minimum time taken to walk from \(A\) to \(G\) is now reduced, but the minimum time taken to walk from \(A\) to \(J\) is not reduced. Find the range of possible values for \(x\). [3]

\includegraphics{figure_4}

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

1. Use Dijkstra's algorithm to find the shortest path from A to F . State the path and its length. On a particular day, Gabriel needs to check each pipe. A route of minimum length, which traverses each pipe at least once and which starts and finishes at A, needs to be found.
2. Use an appropriate algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
3. State the minimum length of Gabriel's route. A new pipe, BG, is added to the network. A route of minimum length that traverses each pipe, including BG, needs to be found. The route must start and finish at A. Gabriel works out that the addition of the new pipe increases the length of the route by twice the length of BG .
4. Calculate the length of BG. You must show your working.

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

1. 1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to H .
   2. State the quickest route. For a network with \(n\) vertices, Dijkstra's algorithm has order \(n ^ { 2 }\)
2. If it takes 1.5 seconds to run the algorithm when \(n = 250\), calculate approximately how long it will take, in seconds, to run the algorithm when \(n = 9500\). You should make your method and working clear.
3. Explain why your answer to part (b) is only an approximation.

1 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to G . Give the route and its length.

6 The network below shows the lengths of roads, in miles, connecting 10 towns, \(A , B , \ldots , J\).

1. Use Dijkstra's algorithm on the network to find the shortest distance from \(A\) to \(J\). Show all your working at each vertex.
2. Write down the corresponding route.
3. A new road is to be constructed connecting \(B\) to \(G\). Find the length of this new road if the shortest distance from \(A\) to \(J\) is reduced by 10 miles. State the new route.
   (3 marks) \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-12_1846_1719_861_150}

7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has eight vertices, \(A , B , \ldots , H\), and edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges \(E H\) and \(G H\) are functions of \(x\) and \(y\). \includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-07_1170_1705_596_164} Given that there are three routes from \(A\) to \(H\) with the same minimum weight, use Dijkstra's algorithm on Figure 2 to find:

1. this minimum weight;
2. the values of \(x\) and \(y\).

2 Answer this question on the insert provided. This diagram shows part of a network. There are other arcs connecting \(D\) and \(E\) to other parts of the network. Apply Dijkstra's algorithm starting from \(A\), as far as you are able, showing your working. Note: you will not be able to give permanent labels to all the vertices shown.

3 Whilst waiting for her meal to be served, Alice tries to construct a network to represent the meals offered in the restaurant. \includegraphics[max width=\textwidth, alt={}, center]{9bb2d545-3764-4930-a8a8-9dc5e25d0836-3_684_1310_365_379}

1. Use Dijkstra's algorithm to find the cheapest route through the undirected network from "start" to "end". Give the cost and describe the route. Use the lettering given on the network in your answer book.
2. Criticise the model and suggest how it might be improved.

4. \begin{figure}[h] \end{figure} The network in Figure 3 shows the roads linking a depot, D, and three collection points \(\mathrm { A } , \mathrm { B }\) and C . The number on each arc represents the length, in miles, of the corresponding road. The road from B to D is a one-way road, as indicated by the arrow.

1. Explain clearly if Dijkstra's algorithm can be used to find a route from D to A . The initial distance and route tables for the network are given in the answer book.
2. Use Floyd's algorithm to find a table of least distances. You should show both the distance table and the route table after each iteration.
3. Explain how the final route table can be used to find the shortest route from D to B . State this route. There are items to collect at \(\mathrm { A } , \mathrm { B }\) and C . A van will leave D to make these collections in any order and then return to D. A minimum route is required. Using the final distance table and the Nearest Neighbour algorithm starting at D,
4. find a minimum route and state its length. Floyd's algorithm and Dijkstra's algorithm are applied to a network. Each will find the shortest distance between vertices of the network.
5. Describe how the results of these algorithms differ.

5 The table shows the weights on the arcs of a network.

1. Draw the network.
2. Apply Dijkstra's algorithm to find the least weight route from G to D. (Do this on the network you drew for part (i).) Give your route and its total weight.
3. Find by inspection the route from \(G\) to \(D\) such that the minimum of the weights for arcs on the route is as large as possible. Give your route and its minimum arc weight. Give an application in which this might be needed.
4. Consider how Dijkstra's algorithm could be modified to solve the problem in part (iii). Explain how to update working values. Explain how to select the next vertex to be permanently labelled.