Shortest path

[ The total weight of the network is 85 ] Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn 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 the shortest path and its length.

On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.

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

The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A.

State the edges that should be repeated.

State a possible route and calculate its length. You must make your method and working clear.

Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.

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

On another day, Sarah wishes to travel from A to F via J.

Find a route of minimal length that goes from A to F via J and state its length.

Use Prim’s algorithm, starting at G, to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.

State the length, in miles, of the minimum spanning tree.

Figure 3 represents a network of roads. The number on each arc is the length, in km, of the corresponding road.

Use Dijkstra’s algorithm to find the shortest route from A to J. State the shortest route and its length.

Explain how you determined the shortest route from your labelled diagram.

Find the shortest route from A to J via E and state its length.

Figure 3 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Liz wishes to travel from S to T.

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

On a particular day, Liz must include F in her route.

Find the shortest path from S to T that includes F, and state its length.

Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either C C₂. A route of minimum length is required. It is decided to use Dijkstra’s algorithm to find the shortest routes between C₁ and J and between C₂ and J.

Explain why J, rather than C₁ or C₂, should be chosen as the starting vertex.

Use Dijkstra’s algorithm to find the shortest route needed to transport the crane. State your route and its length.

A 18 F

Explain what is meant, in a network, by the term path.

Figure 4 represents a network of canals. The number on each arc represents the length, in miles, of the corresponding canal.

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

Write down the length of the shortest path from S to F.

Next week the canal represented by arc AB will be closed for dredging.

Find a shortest path from S to T avoiding AB and state its length.

Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.

Use Dijkstra’s algorithm to find the shortest route from S to T. State your shortest route and its length.

Explain how you determined your shortest route from your labelled diagram.

Due to flooding, the roads in and out of D are closed.

Find the shortest route from S to T avoiding D. State your shortest route and its length.

Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that

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

Explain how you determined your shortest route from your labelled diagram.

The track between E and F is now closed for resurfacing and cannot be used.

Find the shortest route from A to H and state its length.

Figure 1 shows a network of roads between eight villages, A, B, C, D, E, F, G and H. The number on each arc gives the length, in miles, of the corresponding road.

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

State your shortest route.

Write down the shortest route from H to C and state its length.