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.

Write your answer in the Answer Book.

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.

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.

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.

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 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.

Set up the initial time matrix.

Write your answer in the Answer Booklet.

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.

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.

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.