Route inspection

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

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.

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