7.04a Shortest path: Dijkstra's algorithm

\includegraphics{figure_1} Figure 1 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. \hfill [6]

On a particular day Oliver must travel from B to K via A.

1. Find a route of minimal time from B to K that includes A, and state its length. \hfill [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.

1. 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. \hfill [7]

\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_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_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]

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

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]

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

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}

The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.

1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
2. 1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
   2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]

\includegraphics{figure_4}

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

Answer this question on the insert provided. The vertices in the network below represent the junctions between main roads near Ayton (A). The arcs represent the roads and the weights on the arcs represent distances in miles. \includegraphics{figure_4}

1. On the diagram in the insert, use Dijkstra's algorithm to find the shortest path from A to H. You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from A to H and give its length in miles. [7]

Simon is a highways surveyor. He needs to check that there are no potholes in any of the roads. He will start and end at Ayton.

1. Which standard network problem does Simon need to solve to find the shortest route that uses every arc? [1]

The total weight of all the arcs is 67.5 miles.

1. Use an appropriate algorithm to find the length of the shortest route that Simon can use. Show all your working. (You may find the lengths of shortest paths between nodes by using your answer to part (i) or by inspection.) [5]

Suppose that, instead, Simon wants to find the shortest route that uses every arc, starting from A and ending at H.

1. Which arcs does Simon need to travel twice? What is the length of the shortest route that he can use? [2]

There is a set of traffic lights at each junction. Simon's colleague Amber needs to check that all the traffic lights are working correctly. She will start and end at the same junction.

1. Show that the nearest neighbour method fails on this network if it is started from A. [1]
2. Apply the nearest neighbour method starting from C to find an upper bound for the distance that Amber must travel. [3]
3. Construct a minimum spanning tree by using Prim's algorithm on the reduced network formed by deleting node A and all the arcs that are directly joined to node A. Start building your tree at node B. (You do not need to represent the network as a matrix.) Mark the arcs in your tree on the diagram in the insert. Give the order in which nodes are added to your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Amber must travel. [6]

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]

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. \includegraphics{figure_3} \includegraphics{figure_4}

1. Draw the complete network of shortest distances. [2]
2. Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. [2]

A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \includegraphics{figure_5}

1. Draw the extended network and the complete 5-node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.) [3]
2. Produce the shortest distance matrix and the route matrix for the extended 5-node network. [3]
3. Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network. [3]
4. By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm. [4]
5. In the original 5-node network find a shortest route starting at vertex 1 and using each of the 6 arcs at least once. Give the length of your route. [3]

Arthur is planning a bus journey from town \(A\) to town \(L\). There are various routes he can take but he will have to change buses three times -- at \(B\), \(C\) or \(D\), at \(E\), \(F\), \(G\) or \(H\) and at \(I\), \(J\) or \(K\). \includegraphics{figure_2} Fig. 2 Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the total waiting time is as small as possible. Use dynamic programming to find the route that Arthur should use. [8 marks]

The following matrix gives the capacities of the pipes in a system. \begin{array}{c|c|c|c|c|c|c|c} To & & S & T & A & B & C & D
From & & & & & & &
\hline S & & -- & -- & 16 & 26 & -- & --
T & & -- & -- & -- & -- & -- & --
A & & -- & -- & -- & -- & 13 & 5
B & & -- & 16 & -- & -- & -- & 11
C & & -- & 11 & -- & -- & -- & --
D & & -- & 11 & -- & -- & -- & --
\end{array}

1. Represent this information as a digraph. [3 marks]
2. Find the minimum cut, expressing it in the form \(\{\) \(\}|\{\) \(\}\), and state its value. [2 marks]
3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow. [5 marks]
4. Explain how you know that this flow is maximal. [1 mark]

[11 marks]

\includegraphics{figure_1} **Figure 1** [The total weight of the network is \(135 + 4x + 2y\)] The weights on the arcs in Figure 1 represent distances. The weights on the arcs CE and GH are given in terms of \(x\) and \(y\), where \(x\) and \(y\) are positive constants and \(7 < x + y < 20\) There are three paths from A to H that have the same minimum length.

1. Use Dijkstra's algorithm to find \(x\) and \(y\). [7]

An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length.

1. State the arcs that are traversed twice. [1]
2. State the number of times that vertex C appears in the inspection route. [1]
3. Determine the length of the inspection route. [1]