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

Figure 1 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Jan wishes to travel from A to J. She wishes to minimise the distance she travels.

Use Dijkstra’s algorithm to find the shortest path from A to J. Obtain the shortest path and state its length.

On Monday, Jan needs to travel from her gym at J to her home at H via her office at A.

State the shortest path from J to H via A and its length.

On Tuesday, Jan needs to check each road. She must travel along each road at least once. Jan must start and finish at A.

Use the route inspection algorithm to find the length of the shortest inspection route. State the roads that should be repeated. You should make your method and working clear.

On Wednesday, Jan decides to start her inspection route at G but can finish her route at a different node. The inspection route must still traverse each road at least once.

Determine where the route should finish so that the length of the inspection route is minimised. You must give reasons for your answer and state the length of the route.

Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, A, B, C, D, E, F, G, H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible.

The time taken to travel between towns G and J is unknown and is denoted by minutes.

Dijkstra’s algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 below the “Order of labelling” and “Final value” at A and J, and the “Working values” at J, have already been completed.

Use Dijkstra’s algorithm to find the fastest time to travel from A to H. State the quickest route.

Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A. It is given that his route will take at least 440 minutes.

Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of .

Write down a possible route for Ezra.

A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A. It is given that this inspection route takes exactly 488 minutes.

Determine the value of . You must give reasons for your answer.

Figure 4 represents a network of 16 roads in a city. The number on each arc represents the time taken, in minutes, to travel along the corresponding road.

Chan needs to check that the roads are in good repair. He must travel along each road at least once. Chan will start and finish at his office at G and must minimise the total time taken for his inspection route.

For this inspection route,

find the time taken and state a possible route. You must make your method and reasoning clear.

Chan wonders if he can reduce his travel time by starting from his home at B, travelling along each road at least once and finishing at his office at G.

By considering the pairings of all relevant nodes, find any arcs that would need to be traversed twice in the minimum inspection route from B to G. You must make your method clear, showing your working.

Determine which of the two routes ending at G is quicker, the one starting at G or the one starting at B. You must justify your answer.

Figure 3 models a network of cycle lanes that must be inspected. The number on each arc represents the length, in km, of the corresponding cycle lane. Lance needs to cycle along each lane at least once and wishes to minimise the length of his inspection route.

He must start and finish at A.

Use an appropriate algorithm to find the length of the route. State the cycle lanes that Lance will need to traverse twice. You should make your method and working clear.

State the number of times that vertex C appears in Lance’s route.

It is now decided that the inspection route may finish at any vertex. Lance will still start at A and must cycle along each lane at least once.

Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of this new minimum route.

Figure 3 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek’s route. Write down the route that gives this upper bound.

Interpret the route found in (b) in terms of the towns actually visited.

Starting by deleting A and all of its arcs, find a lower bound for the route length.

Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G.

By considering the pairings of all relevant nodes, find the length of Clive’s route. State the edges that need to be traversed twice. You must make your method and working clear.

Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road.

One day, Mabintou wishes to travel from A to H. She wishes to minimise the distance she travels.

Use Dijkstra’s algorithm to find the shortest path from A to H. State your path and its length.

On another day, Mabintou wishes to travel from F to K via A.

Find a route of minimum length from F to K via A and state its length.

The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.

By considering the pairings of all relevant nodes, find the length of James’ route. State the arcs that will need to be traversed twice. You must make your method and working clear.

State the number of times that James will pass through F.

It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.

State the vertex where the new inspection route will finish.

Calculate the difference between the lengths of the two inspection routes.

Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road.

Malcolm wishes to minimise the time spent driving from his home at A to his office at H. The delays from roadworks on two of the roads leading in to H vary daily, and so the time taken to drive along these roads is expressed in terms of , where is fixed for any given day and

Use Dijkstra’s algorithm to find the possible routes that minimise the driving time from A to H. State the length of each route, leaving your answer in terms of where necessary.

On Monday, Malcolm needs to check each road. He must travel along each road at least once. He must start and finish at H and minimise the total time taken for his inspection route.

Malcolm finds that his minimum duration inspection route requires him to traverse exactly four roads twice and the total time it takes to complete his inspection route is 307 minutes.

Calculate the minimum time taken for Malcolm to travel from A to H on Monday. You must make your method and working clear.

Figure 3 models a network of roads. The number on each edge gives the time taken, in minutes, to travel along the corresponding road.

Use Dijkstra's algorithm to find the shortest time needed to travel from A to J. State the quickest route.

Alan needs to travel along all the roads to check that they are in good repair. He wishes to complete his route as quickly as possible and will start at his home, H, and finish at his workplace, D.

By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in Alan's inspection route from H to D. You must make your method and working clear.

For Alan's inspection route from H to D

(i) state the number of times vertex C will appear,

(ii) state the number of times vertex D will appear.

Determine whether it would be quicker for Alan to start and finish his inspection route at H, instead of starting at H and finishing at D. You must explain your reasoning and show all your working.

Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below.

8 17 9 14 18 12 22 10 15 7

Calculate a lower bound for the number of tour groups required. You must make your method clear.

8 17 9 14 18 12 22 10 15 7

Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups.

8 17 9 14 18 12 22 10 15 7

The above list of numbers is to be sorted into descending order.

Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly

Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups.

Figure 2 represents the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum’s entrance at A.

Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.

Write down a possible shortest route, giving its length.

Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.

State the finishing vertex of Sally’s new route and calculate the difference in length between this new route and the route found in (f).