D1 June 2008 Q3

EdexcelOld spec9 marksRoute InspectionShortest Path

3.

Figure 3: network of roads with vertices A to I and lengths in km
Figure 3

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

(a) Use Dijkstra’s algorithm to find the shortest route from A to I. State your shortest route and its length. (5)

Sam has been asked to inspect the network and assess the condition of the roads. He must travel along each road at least once, starting and finishing at A.

(b) Use an appropriate algorithm to determine the length of the shortest route Sam can travel. State a shortest route. (4)

(The total weight of the network is 197km)

‹ Previous32 of 39 in Route InspectionNext ›