AS June 2025 Q3

EdexcelAS paperCurrent spec14 marksRoute Inspection Shortest Path

Figure 2: weighted network on vertices A to J with arcs AB 15, AC 10, AE 14, AG 30, BC 4, BD 3, BH 12, CD 9, CE 2, DE 6, DF 8, DH 6, EF 4, FH 9, FG 10, HJ 8, GJ 3 — Figure 2

[The total weight of the network is 153]

Figure 2 models a network of roads in a town, where the nodes represent road junctions. The numbers on the edges are the times, in minutes, taken to walk along the corresponding roads.

(a) State, with a reason, whether the graph in Figure 2 is Eulerian, semi-Eulerian or neither. (1)

(b)

(i) Use Dijkstra’s algorithm to find the quickest path from A to J.

(ii) State the shortest time needed to walk from A to J. (6)

Ruby manages road maintenance from her office located at junction B. She needs to walk along each road at least once, starting and finishing at her office. Road AE is temporarily blocked so she is unable to walk along it. Ruby wishes to minimise her journey time.

(c)

(i) Use an appropriate algorithm to find the roads that Ruby needs to traverse twice. You must make your method and working clear.

(ii) Calculate Ruby’s journey time. (5)

Ruby can save some time by choosing to start her route from any junction and to finish at her home at A. Road AE is still blocked and Ruby again wishes to minimise her journey time.

(d)

(i) Write down the junction at which Ruby should start.

(ii) Calculate how much time she would save. (2)

Mark scheme (a)

Scheme	Marks	AO
e.g. Graph is semi-Eulerian because exactly two nodes/vertices are of odd degree. D and G are of odd degree.	B1	1.2
	(1)

Notes

a1B1: Correct statement. Accept Semi-Eulerian as only (vertices) D and G are odd (oe). Must include bold text. Condone missing “exactly” and/or “degree”.

Dijkstra labelling: A 1 0; C 2 10; E 3 12 (14 12); B 4 14 (15 14); F 5 16; D 6 17 (19 18 17); H 7 23 (26 25 23); G 8 26 (30 26); J 9 29 (31 29) — Mark scheme (b)

Scheme	Marks	AO
(i)	M1 A1 (ACEB) A1 (FDH) A1ft (GJ)	1.1b 1.1b 1.1b 1.1b
Quickest path A to J is A C E F G J	A1	2.2a
(ii) Shortest time is 29 (minutes)	A1ft	1.1b
	(6)

Mark scheme (c)

Scheme	Marks	AO
(i) A(CB)D + E(F)G = 17 + 14 = 31	M1	3.1b
A(C)E + D(HJ)G = 12 + 17 = 29 *	A1	1.1b
A(CEF)G + DE = 26 + 6 = 32	A1	1.1b
Repeat AC, CE, DH, HJ, JG	A1	2.2a
(ii) Journey time = 153 – 14 + “29” = 168 (minutes)	A1ft	2.2a
	(5)

Notes

ci1M1: Three distinct pairings of A, D, E and G.

ci1A1: Any two rows correct including pairings and totals.

ci2A1: All three rows correct including pairings and totals.

ci3A1: CAO Five correct arcs clearly stated. Must be AC, CE, DH, HJ, JG.

cii1A1ft: CAO ft their “29”, but must be their smallest from a choice of three totals.