D1 January 2010 Q3

EdexcelOld spec10 marksRoute InspectionShortest Path

3.

Figure 3: network with arcs AB 15, AD 20, AC 19, BE 8, BD 14, CD 12, CF 10, DE 2, DG 6, DF 7, EG 3, EH 15, GH 11, FG 4, FH 21
Figure 3

[The total weight of the network is 167]

Figure 3 represents a network of paths.  The number on each arc gives the time, in minutes, to travel along that path.

(a) Use Dijkstra’s algorithm to find the quickest route from A to H.  State your quickest route and the time taken. (5)

Kevin must walk along each path at least once and return to his starting point.

(b) Use an appropriate algorithm to find the time of Kevin’s quickest possible route, starting and finishing at A.  You should make your method and working clear. (5)
‹ Previous29 of 39 in Route InspectionNext ›