Figure 1 represents a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each arc is the time taken, in minutes, to drive along the corresponding road.
Liliya must drive from village A to village H.
(a) (i) Use Dijkstra’s algorithm to determine the fastest route from A to H.
(ii) State the fastest time.
(6)
The roads EF and GJ are now closed for maintenance.
(b) Calculate how much more time Liliya’s drive will now take.
(2)