D1 June 2012 Q5

EdexcelOld spec10 marksShortest Path

5.

Figure 4: network of roads S, A, B, C, D, E, F, T with lengths in miles
Figure 4

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

(a) Use Dijkstra’s algorithm to find the shortest route from S to T. State your shortest route and its length. (6)
(b) Explain how you determined your shortest route from your labelled diagram. (2)

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

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