Shortest Path Algorithms (Edexcel A Level Further Maths: Decision 1): Exam Questions

Figure 2

The network in Figure 2 shows the direct roads linking five villages, A, B, C, D and E.
The number on each arc represents the length, in miles, of the corresponding road.
The roads from A to E and from C to B are one-way, as indicated by the arrows.

Complete the initial distance and route tables for the network provided in the answer book (opens in a new tab).

Write your answer in the Answer Book (opens in a new tab).

Perform the first three iterations of Floyd’s algorithm. You should show the distance table and the route table after each of the three iterations.

After five iterations of Floyd’s algorithm the final distance table and partially completed final route table are shown below.

(i) Explain how the partially completed final route table can be used to find the shortest route from E to A.  

(ii) State this route. 

Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table.

(i) State the cycle obtained using the nearest neighbour algorithm. 

(ii) State the length of this cycle. 

(iii) Interpret the cycle in terms of the actual villages visited.

(iv) Prove that Mabintou’s cycle is not optimal.

Write your answer in the Answer Booklet (opens in a new tab).

Figure 2

Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc.

Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages.

Set up initial time and route matrices.

Write your answer in the Answer Booklet (opens in a new tab).

The matrices after two iterations of Floyd’s algorithm are shown below.

Perform the next two iterations of Floyd’s algorithm that follow from the tables above. You should show the time and route matrices after each iteration.

The final time matrix after completion of Floyd’s algorithm is shown below.

Final time matrix

(i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times.

(ii) Find the time taken for this cycle.

(iii) Interpret the cycle in terms of the actual villages visited.

Figure 4

State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither.

Write your answer in the Answer Booklet (opens in a new tab).

The weights on the arcs in Figure 4 represent distances. The weight on arc  is where and the weight on arc  is where 

An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at  and has a length of 409

It is also given that the length of the shortest route from  to  via  is 140

Using appropriate algorithms, find the value of  and the value of .

Figure 2

Dijkstra’s algorithm has been applied to the network in Figure 2.

A working value has only been replaced at a node if the new working value is smaller.

State the length of the shortest path from A to G.

Complete the table in the answer book (opens in a new tab) giving the weight of each arc listed. (Note that arc CE and arc EF are not in the table.)

State the shortest path from A to G.

It is now given that

• when Prim’s algorithm, starting from A, is applied to the network, the order in which the arcs are added to the tree is AB, BC, CD, CE, EF and FG

• the weight of the corresponding minimum spanning tree is 80

• the shortest path from A to F via E has weight 67

Determine the weight of arc CE and the weight of arc EF, making your reasoning clear.

Figure 3

Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road.

Floyd’s algorithm is to be used to find the complete network of shortest times between the six cities.

An initial route matrix is given in the answer book (opens in a new tab).

Set up the initial time matrix.

Write your answer in the Answer Booklet (opens in a new tab).

Perform the first iteration of Floyd’s algorithm. You should show the time and route matrices after this iteration.

The final time matrix after completion of Floyd’s algorithm is shown below.

A route is needed that minimises the total time taken to traverse each road at least once.

The route must start at B and finish at E.

Use an appropriate algorithm to find the roads that will need to be traversed twice.
You should make your method and working clear.

Write down the length of the route.

Write your answer in the Answer Booklet (opens in a new tab).

Figure 4

In Figure 4 the weights on the arcs represent distances.

(i) Use Dijkstra’s algorithm to find the shortest path from A to H.

(ii) State the length of the shortest path from A to H.

One application of Dijkstra’s algorithm has order , where  is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra’s algorithm from each node of the network.

It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.

Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer.

Explain why your answer to part (b) can only be an approximation.

Figure 3

The network in Figure 3 shows the roads linking a depot, D, and three collection points A, 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.

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 (opens in a new tab).

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.

Explain how the final route table can be used to find the shortest route from D to B.
State this route.

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.

Describe how the results of these algorithms differ.

Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track.

One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.

(i) Use Dijkstra’s algorithm to find the shortest path from A to K.

(ii) State the length of the shortest path from A to K.

The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E.

(i) State the edges that will need to be traversed twice.

(ii) Find the length of Blanche’s route.

It is now decided to start the inspection route at A and finish at K. Blanche must minimise the length of her route and travel along each track at least once.

By considering the pairings of all relevant nodes, find the length of Blanche’s new route. You must make your method and working clear.

The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one‑way only.

Table 1

By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 below.

Floyd’s algorithm is to be used to find the complete network of shortest distances between the six classrooms.

The distance matrix after two iterations of Floyd’s algorithm is shown in Table 2.

Table 2

Perform the next two iterations of Floyd's algorithm that follow from Table 2. You should show the distance matrix after each iteration.

The final distance matrix after completion of Floyd’s algorithm is shown in Table 3.

Table 3

Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.

(i) Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.

(ii) Find the length of each of the two cycles.

(iii) State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka's route.

Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J. The number on each edge gives the length of the corresponding edge.

(i) Use Dijkstra’s algorithm to find the shortest path from A to J.

(ii) State the length of the shortest path from A to J.

One application of Dijkstra’s algorithm has order , where is the number of nodes in the network.

It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.

Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes.

Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.

Use Dijkstra’s algorithm to find the shortest path from A to J.

Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K.

Abi wishes to minimise the total distance required to traverse every track.

By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must

• state which tracks she will repeat in her route

• state the total length of her route

The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H.

Tarig wishes to minimise the total length of his inspection route.

Determine which route, Abi’s or Tarig’s, is shorter. You must make your working clear.