D1 June 2014 (R) Q3

EdexcelOld spec9 marksShortest Path

3.

Figure 3: weighted network of roads with vertices S, A, B, C, D, E, F, G, T
Figure 3

Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to traverse each road.

(a) Use Dijkstra’s algorithm to find the quickest route from S to T. State your quickest route and the time taken. (6)

It is now necessary to include E in the route.

(b) Determine the effect that this will have on the time taken for the journey. You must state your new quickest route and the time it takes. (3)