D1 June 2006 Q4

EdexcelOld spec12 marksGraphs & Networks Shortest Path

(a) Explain what is meant by the term ‘path’. (2)

Figure 3: network of cycle tracks on A to I — Figure 3

Figure 3 shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Mary wishes to cycle from \(A\) to \(I\) as part of a cycling holiday. She wishes to minimise the distance she travels.

(b) Use Dijkstra’s algorithm to find the shortest path from \(A\) to \(I\). Show all necessary working in the boxes in Diagram 1 in the answer book. State your shortest path and its length. (6)

Mary wants to visit a theme park at \(E\).

(d) Find a path of minimal length that goes from \(A\) to \(I\) via \(E\) and state its length. (2)

Mark scheme (a)

Scheme	Marks
A path is a (finite) sequence of edges, such that the end vertex of one edge is the start vertex of the next and in which no vertex appears more than once / no cycles	B2,1,0
	(2)

Notes

B2 A good, complete description

B1 close – mostly there. ‘bod’ gets B1. ‘route’, ‘series’ may be ok.

Dijkstra working: A 1 0; B 2 23; C 3 39; E 4 50; D 5 51; F 6 72; G 7 87; H 8 99; I 9 108 — Mark scheme (b)

Scheme	Marks
	M1 A1 A1 A1ft
shortest path: \(ABDFGI\), length: 108 miles	A1, A1ft
	(6)

Mark scheme (c)

Scheme	Marks
e.g. \(108 - 21 = 87\ \ GI\) \(87 - 15 = 72\ \ FG\) \(72 - 21 = 51\ \ DF\) \(51 - 28 = 23\ \ BD\) \(23 - 23 = 0\ \ AB\) or – trace back from \(I\) – include arc \(XY\) if \(Y\) is already on the path and if the difference in final labels equals the length of arc	B2ft,1ft,0
	(2)

Notes

B2ft complete version of one of the 2 given explanations

B1ft All there bar one step. ‘bod’ gets B1 – easy mark