The Route Inspection Algorithm (Edexcel A Level Further Maths: Decision 1): Exam Questions

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

Figure 1

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

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

(ii) Find the length of Naasir’s new route. 

Figure 2

[The weight of the network is 5x + 246]

Explain why it is not possible to draw a graph with an odd number of vertices of odd valency.

Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road.

Prim’s algorithm, starting at A, is applied to the network. The order in which the arcs are selected is AD, DH, DG, FG, EF, CG, BD. It is given that the order in which the arcs are selected is unique.

Using this information, find the smallest possible range of values for x, showing your working clearly.

A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex.

Given that the time taken to traverse this route is 318 minutes,

Use an appropriate algorithm to determine the value of , showing your working clearly.

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.

Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road.

The table below shows the shortest distances, in miles, between the nine towns.

Table of shortest distances

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

The route must start at F and finish at J.

(i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.

(ii) State the total length of this route.

Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.

Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.

Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound.

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

Pete decides to take the route he found in (c).

Interpret the route in terms of the actual towns visited.

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.