D1 January 2012 Q4

EdexcelOld spec9 marksShortest Path

4.

Figure 5: network with edges AC 37, AD 68, AB 20, BD 45, BE 40, CH 20, CF 48, CD 27, DF 20, DE 12, EG 15, FH 20, FI 15, FG 20, GI 18, HJ 71, IJ 22
Figure 5

Figure 5 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Olivia wishes to travel from A to J as quickly as possible.

(a) Use Dijkstra’s algorithm to find the shortest time needed to travel from A to J. State the shortest route. (7)

On a particular day Olivia must include G in her route.

(b) Find a route of minimal time from A to J that includes G, and state its length (2)
‹ Previous31 of 41 in Shortest PathNext ›