D1 January 2011 Q1

EdexcelOld spec8 marksShortest Path

1.

Figure 1: network with arcs AE 14, AC 9, AB 4, BC 3, BD 10, CE 3, CF 14, CD 2, DF 10, DH 16, EG 4, EF 8, FG 3, FH 4, GH 8
Figure 1

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.

(a) Use Dijkstra’s algorithm to find the shortest distance from A to H. (5)
(b) State your shortest route. (1)
(c) Write down the shortest route from H to C and state its length. (2)
‹ Previous33 of 41 in Shortest PathNext ›