Shortest path

[ The total weight of the network is 413]

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.

[ The total weight of the network is 299]

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.

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

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.

State the edges that will need to be traversed twice.

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.

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.

A 57 B

[ The total weight of the network is 1648]

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.

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.

In Figure 4 the weights on the arcs represent distances.

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

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

One application of Dijkstra’s algorithm has order n², where n 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.

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 total weight of the network is 320 + x + y ]

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

The weights on the arcs in Figure 4 represent distances. The weight on arc EF is x where 12 x 26 and the weight on arc DG is y where 0 y 10

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

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

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

[ The total weight of the network is 370]

Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.

Use Dijkstra’s algorithm to find the shortest path from A to D, stating the path and its length.

On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G.

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

Find the length of Naasir’s route.

On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B.

Determine the possible starting and finishing points so that the length of Naasir’s route is minimised. You must give reasons for your answer.

Find the length of Naasir’s new route.

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.