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

Write your answer in the Answer Booklet.

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.