D1 January 2009 Q6

EdexcelOld spec7 marksShortest Path

6.

Figure 4: network of roads through villages A to H with lengths in km
Figure 4

Figure 4 shows a network of roads through eight villages, A, B, C, D, E, F, G and H. The number on each arc is the length of that road in km.

(a) Use Dijkstra’s algorithm to find the shortest route from A to H. State your shortest route and its length. (5)

There is a fair in village C and you cannot drive through the village. A shortest route from A to H which avoids C needs to be found.

(b) State this new minimal route and its length. (2)
‹ Previous37 of 41 in Shortest PathNext ›