Travelling salesman problem

The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.

State the weight of the minimum spanning tree found in part (a).

Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.

A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.

Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route.

Use the nearest neighbour algorithm, starting at D, to find an upper bound for the length of the historian’s route.

Write down the route which gives this upper bound.

Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles was found.

State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.

By deleting A and all of its arcs, find a lower bound for the length of the historian’s route.

By deleting J and all of its arcs, a lower bound of length 274 miles was found.

State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.

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.

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

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.

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.

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

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

Find the length of each of the two cycles.

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

Table 1 shows the shortest distances, in miles, between eight towns, A, B, C, D, E, F, G and H.

Use Prim’s algorithm, starting at A, to find the minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges of your tree.

State the weight of the minimum spanning tree.

Table 2 shows the distances, in miles, between town J and towns A, B, C, D, E, F, G and H.

Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.

Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav’s route. You must state your route and its length.

Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav’s route.

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.

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

Time matrix
Route matrix

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

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

Find the time taken for this cycle.

Interpret the cycle in terms of the actual villages visited.

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.

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.

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

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.

State the cycle obtained using the nearest neighbour algorithm.

State the length of this cycle.

Interpret the cycle in terms of the actual villages visited.

Prove that Mabintou’s cycle is not optimal.