AS June 2018 Q1

EdexcelAS paperCurrent spec9 marksAlgorithms Shortest Path

Figure 1: network on vertices A to J with arcs AB 3, AD 25, AI 12, BC 5, CD 14, CE 6, DE 7, EF 8, EG 16, IF 7, IJ 10, FG 9, GH 11, JH 23 — Figure 1

Figure 1 represents a network of roads.
The number on each arc represents the time taken, in minutes, to drive along the corresponding road.

(a)

(i) Use Dijkstra’s algorithm to find the shortest time needed to travel from A to H.

(ii) State the quickest route. (6)

For a network with \(n\) vertices, Dijkstra’s algorithm has order \(n^2\)

(b) If it takes 1.5 seconds to run the algorithm when \(n = 250\), calculate approximately how long it will take, in seconds, to run the algorithm when \(n = 9500\). You should make your method and working clear. (2)

Dijkstra labelling: A 1 0; B 2 3; C 3 8; I 4 12; E 5 14; F 6 19 (19 (22)); D 7 21 (25 22 21); J 8 22; G 9 28 (30 28); H 10 39 (45 39) — Mark scheme (a)

Scheme	Marks	AO
(i)	M1 A1 A1 A1ft	1.1b 1.1b 1.1b 1.1b
Shortest time to travel from A to H is 39 minutes	A1ft	1.1b
(ii) Quickest route is AIFGH	A1	1.1b
	(6)

Mark scheme (b)

Scheme	Marks	AO
\(1.5 \times \left(\dfrac{9500}{250}\right)^2\)	M1	1.1a
= 2166 seconds	A1	1.1b
	(2)

Notes

M1 Complete method – allow 250/9500 (but must be squared) – allow slips in values e.g. 950 for 9500

A1: Cao (accept 2170 but only with correct working) – accept 2166 with no working for M1 only

Mark scheme (c)

Scheme	Marks	AO
order of \(n^2\) does not mean that the order is proportional to \(n^2\) (which is the assumption behind the answer in (b)) but merely means that the dominant term is of order \(n^2\)	B1	3.2b
	(1)
	(9 marks)

Notes

B1: Any indication that the run-time is not exactly proportional to \(n^2\) e.g. may suggest that there are other terms (\(n^2 + \ldots\)), or that \(n^2\) is the dominant term, or that order does not imply proportionality. Do not accept only that ‘\(n^2\) is not exact’.