Route Inspection

Topic

From an AS paper

Edexcel

Edexcel · Old spec

A2 June 2025 Q4

EdexcelCurrent spec13 marksRoute Inspection Shortest Path

Figure 2: network on offices A to K with edges AB 13, AC 5, AD 17, BC 6, BE 24, BF 10, BJ 39, CF 17, CG 9, CD 11, DG 1, DH 25, DK 19, EJ 10, FG 4, FK 13, GK 22, HK 7, JK 16 — Figure 2

[The total weight of the network is 268]

Figure 2 represents a network of corridors between 10 offices, A, B, C, D, E, F, G, H, J and K, in a building. The number on each edge represents the length, in metres, of the corresponding corridor.

On Monday morning, Turvi needs to walk from J to K via A. She wishes to minimise the distance she travels along the corridors.

(a)

(i) Use Dijkstra’s algorithm, starting at A, to find the shortest route from J to K via A.

(ii) State the length of this route. (6)

On Monday afternoon, Turvi needs a route that traverses each corridor at least once. She plans to start at J and finish at A and wants to minimise the distance travelled.

(b)

(i) By considering the pairings of all relevant nodes, find the corridors that would need to be traversed twice. You must make your method and working clear.

(ii) State the total length of this route. (5)

Turvi discovers that she cannot walk along corridors AB, CD and JK because they are being decorated. Turvi walks from J to A travelling along all the other corridors at least once. She does this in the minimum distance possible.

(c) Determine the difference between the length of the route Turvi travels and the length of the route found in (b). You must make the values used in your calculation clear. (2)

Dijkstra labelling from A: A 1 0; C 2 5 (5); B 3 11 (13 11); G 4 14 (14); D 5 15 (17 16 15); F 6 18 (22 21 18); K 7 31 (36 34 31); E 8 35 (35); H 9 38 (40 38); J 10 45 (50 47 45) — Mark scheme (a)

Scheme	Marks	AO
	M1 A1 (ACBGD) A1 (FKE) A1ft (HJ)	1.1b 1.1b 1.1b 1.1b
(i) Route from J to K via A: JEBCACGFK	A1	2.2a
(ii) Length of shortest route from J to K via A is 76 (m)	A1ft	2.2a
	(6)

Mark scheme (b)

Scheme	Marks	AO
(i) BC + D(GF)K = 6 + 18 = 24	M1	3.1b
B(FG)D + C(GF)K = 15 + 26 = 41	A1	1.1b
B(F)K + C(G)D = 23 + 10 = 33	A1	1.1b
Edges to traverse twice are BC, DG, FG, FK	A1	2.2a
(ii) Length of route = 268 + 24 = 292 (m)	A1ft	2.2a
	(5)

Notes

bi1M1: The correct three pairings of the correct four nodes (B, C, D and K)

bi1A1: Two rows correct including pairings and totals

bi2A1: All three rows correct including pairings and totals

bi3A1: Correct repeats (BC, DG, FG, FK)

bii4A1ft: Length of route correct on the follow through (268 + smallest repeat) but must be from a choice of 3 totals

Mark scheme (c)

Scheme	Marks	AO
E.g. [ 24 – ] (“45” – 13 – 11 – 16) Or [292 – ] (268 + “45” – (13 + 11 + 16))	M1	3.1b
= 19 (m)	A1	2.2a
	(2)
	(13 marks)

Notes

c1M1: For using their final value at J and the blocked lengths in attempt to work out the length or change in length of the new route (sight of “45” 13 11 and 16) (follow through their final value at J for this mark) (condone use of 40 for 13 + 11 + 16)

c1A1: CAO (19)

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.

Scheme	Marks	AO
(i) Start at G	B1	2.2a
(ii) 23 (minutes)	B1	2.2a
	(2)
	(14 marks)

A2 June 2024 Q3

EdexcelCurrent spec13 marksRoute Inspection Shortest Path

Figure 1: network on towns A to K with arcs AB 25, AC 18, AD 47, BC 5, BD 17, CD 24, DE 20, DF 34, DG 26, EF 12, EJ 41, EK 37, FK 25, FJ 27, FG 4, FH 15, GH 21, JH 9, KH 6 — Figure 1

[The total weight of the network is 413]

Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track.

(a) Use Dijkstra’s algorithm to find the shortest path from A to J. (5)

Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K.

Abi wishes to minimise the total distance required to traverse every track.

(b) By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must

state which tracks she will repeat in her route
state the total length of her route

(6)

The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H.

Tarig wishes to minimise the total length of his inspection route.

Dijkstra labelling from A: A 1 0; C 2 18 (18); B 3 23 (25 23); D 4 40 (47 42 40); E 5 60 (60); G 6 66 (66); F 7 70 (74 72 70); H 8 85 (87 85); K 9 91 (97 95 91); J 10 94 (101 97 94) — Mark scheme (a)

Scheme	Marks	AO
	M1 A1 (ABCDE) A1 (GFH) A1ft (JK)	1.1b 1.1b 1.1b 1.1b
Shortest path from A to J is ACBDGFHJ	A1	2.2a
	(5)

Mark scheme (b)

Scheme	Marks	AO
If finishing at J then pair A, B, C and K: AB + CK = 23 + 73 = 96 AC + BK = 18 + 68 = 86* AK + BC = 91 + 5 = 96	M1 A1ft	3.1b 1.1b
If finishing at K then pair A, B, C and J: AB + CJ = 23 + 76 = 99 AC + BJ = 18 + 71 = 89 AJ + BC = 94 + 5 = 99	M1 dep A1ft	1.1b 1.1b
Finish at J and repeated AC, BD, DG, GF, FH, HK	A1	2.2a
Total length of route is 413 + 86 = 499 (km)	A1ft	2.2a
	(6)

Notes

(b) Note: FT marks here are only for their values at K and J

M1: One correct set (either ABCK or ABCJ) of three distinct pairings of the correct four odd nodes (so must have AB + CK, AC + BK and AK + BC or AB + CJ, AC + BJ and AJ + BC)

A1ft: Any three rows correct including pairings and totals, from either set ABCK or set ABCJ (this can be 3 correct from one set or 2 correct from one set and 1 correct from the other set)

dM1: All six distinct pairings for nodes ABCK and ABCJ – dependent on first M mark

A1ft: All six rows correct including pairings and totals

A1: cao correct edges clearly stated and not just in their working. Must be edges AC, BD, DG, GF, FH, HK and clearly selecting to finish at J

A1ft: Either 499 from correct working or 413 + their “86” – dependent on first four marks in this part

To check pairings use

AB	CK	96 or Final value at K + 5
AC	BK	86 or Final value at K - 5
AK	BC	96 or Final value at K + 5

AB	CJ	99 or Final value at J + 5
AC	BJ	89 or Final value at J - 5
AJ	BC	99 or Final value at J + 5

Mark scheme (c)

Scheme	Marks	AO
e.g. Tarig’s route length: (94 + 2) – 5 – 6 = 85 or with the addition of 413 giving 413 + 94 + 2 – 5 – 6 = 498 or 402 (413 – 5 – 6) + 96 (AJ) = 498	M1	3.1b
Therefore Tarig’s route is shorter (dependent on 498 and 499 or 85 and 86 seen)	A1	2.2a
	(2)
	(13 marks)

Notes

M1: Calculating the length of Tarig’s route by considering the length of shortest path from A to J (either 94 or follow through final value at J from (a)) + 2 (as we can no longer take the shortest path from A to D as BC has been removed) – 5 (BC) – 6 (HK) A correct value of 498 or 85 implies this mark (but not from incorrect working)

A1: CAO (dependent on obtaining both correct values of 499 and 498 or 86 and 85)

AS June 2024 Q3

EdexcelAS paperCurrent spec11 marksRoute Inspection Shortest Path

Figure 3: weighted network on vertices A to M with arcs AB 2, AC 9, AD 14, AE x, BC 5, BF 12, CF 6, CG 23, CH 15, DH 7, EJ 6, JH 1, FK 2, FG 13, GH 6, GM 10, KM y, HL 5, LM 3 — Figure 3

[The total weight of the network is \(139 + x + y\)]

(a) Explain what is meant by the term “tree”. (1)

Figure 3 represents a network of walkways in a warehouse.
The arcs represent the walkways and the nodes represent junctions between them.
The number on each arc represents the length, in metres, of the corresponding walkway.

The values \(x\) and \(y\) are unknown, however it is known that \(x\) and \(y\) are integers and that

\[9 \lt x \lt y \lt 14\]

(b)

(i) Use Dijkstra’s algorithm to find the shortest route from A to M.

(ii) State an expression for the length of the shortest route from A to M. (6)

The warehouse manager wants to check that all of the walkways are in good condition.

Their inspection route starts at B and finishes at C.

The inspection route must traverse each walkway at least once and be as short as possible.

(d) State the number of times that H appears in the inspection route. (1)

The warehouse manager finds that the total length of the inspection route is 172 metres.

(e) Determine the value of \(x\) and the value of \(y\) (2)

Mark scheme (a)

Scheme	Marks	AO
A tree is a connected graph with no cycles	B1	1.2
	(1)

Notes

B1: Must state connected graph and must state no cycles. Paths and/or loops are NOT correct, ignore any extras unless incorrect.

Dijkstra labelling: A 1 0; B 2 2; C 3 7 (9 7); E 4 x; F 5 13 (14 13); D 6 14; K 7 15; J 8 x+6; H 9 x+7 (22 21 x+7); L 10 x+12; G 11 x+13 (30 26 x+13); M 12 x+15 (y+15 x+15) — Mark scheme (b)

Scheme	Marks	AO
(i)	M1 A1 (A,B,C, E,F,K) A1 (D,J,H) A1ft (G,L,M)	1.1b 1.1b 1.1b 1.1b
Shortest route from A to M is AEJHLM	A1	2.2a
(ii) Length of shortest route is \(x + 15\)	A1ft	2.2a
	(6)

Scheme	Marks	AO
Arcs HL and LM need to be traversed twice	B1	1.1b
	(1)

Scheme	Marks	AO
H would appear 3 times	B1	2.2a
	(1)

Mark scheme (e)

Scheme	Marks	AO
\(139 + x + y + 5 + 3 = 172\)	M1	1.1b
\(x + y = 25\) \(x = 12,\ y = 13\)	A1	2.2a
	(2)
	(11 marks)

Notes

M1: setting the total weight of the network (\(139 + x + y\)) plus 8 (or their repeated arcs) equal to 172

A1: CAO both values clearly assigned; \(x\)=12, \(y\)=13. Dependent on the correct repeated arcs [accept as a minimum sight of H and M and 8 (5+3) here] in part (c)
If you just see \(x\)=12, \(y\)=13 stated with no working, M0A0.

A2 June 2023 Q5

EdexcelCurrent spec13 marksMinimum Spanning Trees Route Inspection Travelling Salesman

Figure 5: network on A to J with arcs AB 34, AG 8, AF 20, AD 42, BE 50, BH 21, BC 17, GD 23, GF 48, FD 22, FE 65, CE 33, CJ 10, HJ 12, EJ 18 — Figure 5

[The total weight of the network is 423]

Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road.

The table below shows the shortest distances, in miles, between the nine towns.

	A	B	C	D	E	F	G	H	J
A	–	34	51	31	79	20	8	55	61
B	34	–	17	65	45	54	42	21	27
C	51	17	–	82	28	71	59	22	10
D	31	65	82	–	87	22	23	86	92
E	79	45	28	87	–	65	87	30	18
F	20	54	71	22	65	–	28	75	81
G	8	42	59	23	87	28	–	63	69
H	55	21	22	86	30	75	63	–	12
J	61	27	10	92	18	81	69	12	–

Table of shortest distances

A route is needed that minimises the total distance required to traverse each road at least once.

The route must start at F and finish at J.

(a)

(i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice.

(ii) State the total length of this route. (5)

(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3)

Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels.

(c) Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound. (2)

(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)

Pete decides to take the route he found in (c).

(e) Interpret the route in terms of the actual towns visited. (1)

Mark scheme (a)

Scheme	Marks	AO
(i) Route must start at F and finish at J therefore need to consider pairings of the nodes F, C, D and G	M1	3.1b
CD + FG = 82 + 28 = 110 CF + DG = 71 + 23 = 94 CG + DF = 59 + 22 = 81	A1 A1	1.1b 1.1b
Repeated roads: CB, BA, AG, and DF	A1	2.2a
(ii) Length of route = 423 + 81 = 504 (miles)	A1ft	2.2a
	(5)

Notes

M1: The correct three pairings of the correct four nodes (F, C, D and G)

A1: Two rows correct including pairings and totals

A1: All three rows correct including pairings and totals

A1: CAO (CB, BA, AG, DF only but in any order) – must be stated as edges so A0 for any of CG or CBAG or CG via B and A

A1ft: 423 + weight of their shortest pairing

Mark scheme (b)

Scheme	Marks	AO
Prim’s starting at A: AG, AF, DF, AB, BC, CJ, HJ, EJ	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: First three arcs correctly chosen in order {AG, AF, DF, …} or first four nodes correctly chosen in order{A, G, F, D,…}. If any explicit rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of one of the tables{1, -, -, 4, -, 3, 2, -, -} so please check the top of the tables carefully

A1: First five arcs correctly chosen in order {AG, AF, DF, AB, BC, …} or all nine nodes correctly chosen in order{A, G, F, D, B, C, J, H, E}. Order of nodes may be seen at the top of one of the tables so for the first two marks accept {1, 5, 6, 4, 9, 3, 2, 8, 7} (do not condone any missing numbers e.g. the number 9 must be above E)

A1: CSO – all arcs correct stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of one of the tables unless the correct list of arcs (in the correct order) is also seen)

Mark scheme (c)

Scheme	Marks	AO
NNA starting at G: G – A – F – D – B – C – J – H – E – G 8 + 20 + 22 + 65 + 17 + 10 + 12 + 30 + 87 = 271	M1 A1	1.1b 1.1b
	(2)

Notes

M1: Nearest neighbour route starting at G – must have at least G – A – F – D – B – C – … allow if stated in terms of arcs

A1: CAO on length (271) and route (must return to G and can be stated in terms of arcs)

Mark scheme (d)

Scheme	Marks	AO
(141 – 8) + 8 + 23 = 164 (miles)	M1 A1	3.1b 2.2a
	(2)

Notes

M1: For one of the following

RMST arcs: AF, DF, AB, BC, CJ, HJ, EJ (stated in any order) – condone AG added too but must be removed at some later stage (e.g. subtracting 8 at some point)
RMST weight calculation: 20 + 22 + 34 + 17 + 10 + 12 + 18 (not just 20, 22, etc.)
RMST weight stated: 133 or 141 – 8
Lower bound stated: 164

A1: CAO (164)

Scheme	Marks	AO
GAFD GA BCJH J E JCBA G	B1	3.2a
	(1)
	(13 marks)

AS June 2023 Q5

EdexcelAS paperCurrent spec8 marksGraphs & Networks Route Inspection

Figure 4: network with arcs AB 2x + 1, AC x + 5, BC 5x - 8, BD x + 4, CD 2x - 2, CE 3x + 2, CF x + 7, EF 5x - 6 — Figure 4

[The weight of the network is \(20x + 3\)]

Figure 4 shows a graph G that contains 8 arcs and 6 vertices.

(a) State the minimum number of arcs that would need to be added to make G into an Eulerian graph. (1)

(b) Explain whether or not the route A – C – F – E – C – D – B is an example of a path on G. (1)

Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.

You are given that \(x \gt 1.6\)

A route is required that

starts and finishes at the same vertex
traverses each road at least once
minimises the total time taken

The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes.

Given that the inspection route contains two roads that need to be traversed twice,

Scheme	Marks	AO
1	B1	1.2
	(1)

Mark scheme (b)

Scheme	Marks	AO
The route is not an example of a path as vertex C appears twice	B1	2.4
	(1)

Notes

(b) B1: No + correct reason – no bod – must refer to C appearing twice (not just that a vertex is repeated) or that it contains the cycle C – F – E – C (not just that it contains a cycle). All technical language must be correct if used for this mark and do not isw any incorrect reasoning (for example if they imply that a path must pass through every vertex)

Mark scheme (c)

Scheme	Marks	AO
As the route contains two roads that need to be traversed twice this means that either the pairing AB, AC or BD, CD needs to be repeated	B1	2.1
AB + AC = \(3x + 6\) and BD + CD = \(3x + 2\) and as \(3x + 6 \gt 3x + 2\) (for all values of \(x\)) this means that BD + CD are repeated	B1	2.2a
Because two roads are repeated in the shortest inspection route this means that \(5x - 8 \gt 3x + 2\)	M1	3.1b
\(x \gt 5\)	A1	1.1b
\((20x + 3) + (3x + 2) \leqslant 189\)	M1	3.4
\(x \leqslant 8\)	A1	2.2a
	(6)
	(8 marks)

Notes

(c) B1: Recognising that one of the two pairings between B and C containing two arcs will need to be repeated. For example, might state BAC or BDC or BA, AC or BD, DC (as an indication of considering the two odd nodes B and C together with one of the two paths via A and D) or one of the expressions \(3x + 6\) or \(3x + 2\) (or correct but unsimplified) seen would score this mark. Condone for this mark those candidates who consider the direct arc BC (provided at least one of the pairings via A or D is considered too)

B1: Correct deduction that BD + CD needs to be repeated (or that AB + AC is not repeated). Allow stating that \(3x + 2\) is ‘better’ than \(3x + 6\) or simply stating both expressions and selecting \(3x + 2\) (but we must see both simplified expressions for this mark). This selection of \(3x + 2\) (after seeing both expressions) could be implied by forming an equation/inequality with only this expression. This mark cannot be awarded if either of the other two inequalities/equations e.g. \((20x + 3) + (3x + 6) \leqslant 189\) or \((20x + 3) + (5x - 8) \leqslant 189\) are formed, unless they are explicitly rejected with the correct reason (that is because \(3x + 6 \gt 3x + 2\) and because the route contains two roads). Obtaining \(x \leqslant 7.826\ldots\) and/or \(x \leqslant 7.76\) and simply rejecting these without the valid reasons as stated above does not score this mark

M1: Considers explicitly the direct route between B and C (\(5x - 8\)) and compares this (in the form of a linear equation or inequality) with either of the two pairings AB + AC or BD + CD

A1: cao (\(x \gt 5\))

M1: (\(20x + 3\)) + (either their \(3x + 6\) or their \(3x + 2\)) together with 189 (allow equals or any inequality)

A1: cao (\(x \leqslant 8\))

If full marks would have been awarded in (c) but any other inequalities apart from \(x \gt 5\) and \(x \leqslant 8\) are found, then withhold the second B mark

AS June 2022 Q3

EdexcelAS paperCurrent spec14 marksRoute Inspection Shortest Path

Figure 2: weighted network on vertices A to H with arcs AB 4, AC 12, AD 10, BC 7, BF 15, BE 13, CF 3, DF 8, DG 11, EF 4, EH 5, FH 10, FG 6, GH 12 — Figure 2

[The total weight of the network is 120]

(a) Explain what is meant by the term “path”. (2)

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

Figure 2 represents a network of cycle tracks between eight villages, A, B, C, D, E, F, G and H. The number on each arc represents the length, in km, of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H.

An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G.

Daisy plans to cycle along every track in the new network, starting and finishing at H.

Given that the addition of either track CD or track EG will not affect the final values obtained in (c),

(d) use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must

state which tracks Daisy will repeat in her route
state the total length of her route

(6)

Mark scheme (a)

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

Notes

B1: One of the three points made clearly (‘finite, edges’, ‘end vertex of one edge is the start vertex of the next’, ‘no vertex appears more than once’ – condone ‘a vertex cannot appear twice’ but not ‘a vertex cannot be repeated more than once’)

B1: All three points made clearly. Candidates who state that a path is a walk in which no vertex appears more than once can score B1B0 only

Mark scheme (b)

Scheme	Marks	AO
Graph is neither Eulerian nor semi-Eulerian because it has six odd vertices.	B1	2.4
	(1)

Notes

B1: Correct statement (neither) with correct reason. Either states that there are more than two odd nodes or does not have exactly zero or two odd nodes or that there are six odd nodes. Their argument must be convincing that the graph cannot be Eulerian or semi-Eulerian (e.g. ‘the network does not have two odd nodes’ is B0). Do not ISW (or BOD) if any incorrect reasoning given

Dijkstra labelling: A 1 0; B 2 4 (4); D 3 10 (10); C 4 11 (12 11); F 5 14 (19 18 14); E 6 17 (17); G 7 20 (21 20); H 8 22 (24 22) — Mark scheme (c)

Scheme	Marks	AO
	M1 A1 (ABDC) A1 (FE) A1ft (GH)	1.1b 1.1b 1.1b 1.1b
Shortest path: ABEH	A1	2.2a
	(5)

Mark scheme (d)

Scheme	Marks	AO
If arc CD included: AE + GH = 17 + 12 = 29 AG + EH = 20 + 5 = 25 AH + EG = 22 + 10 = 32	M1 A1	3.1b 1.1b
If arc EG included: AC + DH = 11 + 17 = 28 AD + CH = 10 + 12 = 22* AH + CD = 22 + 11 = 33	depM1 A1	1.1b 1.1b
Track EG with repeated arcs AD, CF, FE, EH Length = 120 + 9 + 22 = 151 (km)	A1 A1	2.2a 2.2a
	(6)
	(14 marks)

Notes

M1: One correct set (either AEGH or ACDH) of three distinct pairings of the correct four odd nodes (so must have AE + GH, AG + EH and AH + EG or AC + DH, AD + CH and AH + CD)

A1: Any three rows correct including pairings and totals, from either set AEGH or set ACDH

dM1: All six distinct pairings for nodes AEGH and ACDH – dependent on first M mark

A1: All six rows correct including pairings and totals

A1: cao correct edges clearly stated and not just in their working. Must be edges AD, CF, FE, EH and clearly selecting track EG

A1: cao (151) from correct working – dependent on first four marks in this part

A2 June 2022 Q2

EdexcelCurrent spec13 marksRoute Inspection Shortest Path

Figure 1: network on A, B, C, D, E, F, G, H, J and K with edges AB 8, AC 18, AD 14, BC 9, BE 4, BH 23, CE 3, CF 10, DF 14, DG 25, EF 17, EG 31, EH 16, FG 10, GH 6, GJ 10, GK 25, HJ 23, HK 33 — Figure 1

[The total weight of the network is 299]

Figure 1 represents a network of cycle tracks between 10 landmarks, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding track.

One day, Blanche wishes to cycle from A to K. She wishes to minimise the distance she travels.

(a)

(i) Use Dijkstra’s algorithm to find the shortest path from A to K.

(ii) State the length of the shortest path from A to K. (6)

The cycle tracks between the landmarks now need to be inspected. Blanche must travel along each track at least once. She wishes to minimise the length of her inspection route. Blanche will start her inspection route at D and finish at E.

(b)

(i) State the edges that will need to be traversed twice.

(ii) Find the length of Blanche’s route. (2)

It is now decided to start the inspection route at A and finish at K. Blanche must minimise the length of her route and travel along each track at least once.

(c) By considering the pairings of all relevant nodes, find the length of Blanche’s new route. You must make your method and working clear. (5)

Dijkstra boxes (vertex, order of labelling, final value; working values): A 1, 0; B 2, 8 (8); E 3, 12 (12); D 4, 14 (14); C 5, 15 (18 17 15); F 6, 25 (29 28 25); H 7, 28 (31 28); G 8, 34 (43 39 35 34); J 9, 44 (51 44); K 10, 59 (61 59) — Mark scheme (a)

Scheme	Marks	AO
(i)	M1 A1 A1 A1ft	1.1b 1.1b 1.1b 1.1b
Path from A to K: ABEHGK	A1	2.2a
(ii) Length of shortest path from A to K is 59 (km)	A1ft	2.2a
	(6)

Mark scheme (b)

Scheme	Marks	AO
(i) Repeated edges: AB, BE, EH	B1	2.2a
(ii) Length of route = 299 + 28 = 327 (km)	B1ft	2.2a
	(2)

Notes

(b)(i) B1: cao (AB, BE, EH only but in any order) – must be stated as edges so B0 for ABEH

(ii) B1ft: 327 or follow through their final value at H from (a) + 299

Mark scheme (c)

Scheme	Marks	AO
Route must start at A and finish at K therefore need to consider pairings of the nodes D, E, H and K	M1	3.1b
D(AB)E + H(G)K = 26 + 31 = 57 D(FG)H + E(HG)K = 30 + 47 = 77 D(FG)K + EH = 49 + 16 = 65	A1 A1 A1	1.1b 1.1b 1.1b
Length of new route = 299 + 57 = 356 (km)	A1	2.2a
	(5)
	(13 marks)

Notes

(c) M1: The correct three pairings of the correct four nodes (D, E, H and K)

A1: One row correct including pairing and total

A1: Two rows correct including pairings and totals

A1: All three rows correct including pairings and totals

A1: cao (356) – dependent on all previous marks in this part

Condone lack of units throughout

A2 October 2021 Q4

EdexcelCurrent spec8 marksRoute Inspection Shortest Path

Figure 3: network on A, B, C, D, E and F with arcs AB 57, AC 95, AD 150, AE 63, AF 230, BC 72, BE 132, CD 289, CE 160, CF 125, DE 84, EF 191 — Figure 3

[The total weight of the network is 1648]

Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road.

Floyd’s algorithm is to be used to find the complete network of shortest times between the six cities.

An initial route matrix is given in the answer book.

Initial route matrix (answer book)

	A	B	C	D	E	F
A	A	B	C	D	E	F
B	A	B	C	D	E	F
C	A	B	C	D	E	F
D	A	B	C	D	E	F
E	A	B	C	D	E	F
F	A	B	C	D	E	F

(a) Set up the initial time matrix. (1)

(b) Perform the first iteration of Floyd’s algorithm. You should show the time and route matrices after this iteration. (2)

The final time matrix after completion of Floyd’s algorithm is shown below.

	A	B	C	D	E	F
A	–	57	95	147	63	220
B	57	–	72	204	120	197
C	95	72	–	242	158	125
D	147	204	242	–	84	275
E	63	120	158	84	–	191
F	220	197	125	275	191	–

A route is needed that minimises the total time taken to traverse each road at least once.

The route must start at B and finish at E.

(c) Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear. (4)

(d) Write down the length of the route. (1)

Mark scheme (a)

Scheme

Marks

Initial time matrix

	A	B	C	D	E	F
A	-	57	95	150	63	230
B	57	-	72	∞	132	∞
C	95	72	-	289	160	125
D	150	∞	289	-	84	∞
E	63	132	160	84	-	191
F	230	∞	125	∞	191	-

1.1b

(1)

Notes

(a) B1: Correct distance table (condone dashes, crosses, etc. for infinity but do not condone a ‘large’ number in these cells or these cells left blank)

Mark scheme (c)

Scheme	Marks	AO
Route must start and finish at B, E therefore need to consider pairings of the other four odd nodes (A, C, D and F)	M1	3.1b
AC + DF = 95 + 275 = 370 AD + CF = 147 + 125 = 272* AF + CD = 220 + 242 = 462	A1 A1	1.1b 1.1b
Repeat arcs: AE, DE and CF	A1	2.2a
	(4)

Notes

(c) M1: Either the correct three pairings of the correct four nodes A, C, D and F or recognises that as the route begins at B and finishes at E that only the nodes A, C, D and F need to be considered

A1: Two rows correct including pairings and totals

A1: All three rows correct including pairings and totals

A1: selecting the shortest pairing, and stating that these arcs (AE, DE and CF) should be repeated. Must be these arcs and not e.g., AED or AD via E, etc.

Scheme	Marks	AO
Length: 1648 + 272 = 1920 (minutes)	B1	2.2a
	(1)
	(8 marks)

A2 October 2020 Q6

EdexcelCurrent spec11 marksRoute Inspection Shortest Path

Figure 4: network on A to G with arcs AB 24, AC 42, AD 65, BC 15, CE 19, CF 45, CD 21, CG 31, DF 34, DG y, EF x, FG 24 — Figure 4

[The total weight of the network is \(320 + x + y\)]

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

The weights on the arcs in Figure 4 represent distances. The weight on arc EF is \(x\) where \(12 \lt x \lt 26\) and the weight on arc DG is \(y\) where \(0 \lt y \lt 10\)

An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at A and has a length of 409

It is also given that the length of the shortest route from F to G via A is 140

(b) Using appropriate algorithms, find the value of \(x\) and the value of \(y\). (9)

Mark scheme (a)

Scheme	Marks	AO
The graph has exactly two odd nodes and so the graph is semi-Eulerian	B1 dB1	2.4 2.2a
	(2)

Notes

(a) B1: Explanation which consists of the graph having two odd nodes or stating graph is semi-Eulerian

dB1: Exactly two odd nodes (or two odd nodes and five even nodes or the rest even) together with the deduction that therefore the graph is semi-Eulerian

Dijkstra labelling from A: A 1 0 (0); B 2 24 (24); C 3 39 (42 39); E 4 58 (58); D 5 60 (65 60); G 6 60 + y (70 60 + y); F 7 58 + x (84 58 + x) — Mark scheme (b)

Scheme	Marks	AO
	M1 A1 A1 A1	1.1b 1.1b 1.1b 1.1b
Shortest path from A to F is \(58 + x\) and shortest path from A to G is \(60 + y\)	A1ft	2.2a
\(58 + x + 60 + y = 140\)	M1	2.1
The only odd nodes in the network are A and G	B1	2.2a
Route inspection algorithm: Shortest route between A and G is \(60 + y\) \(\Rightarrow\ 320 + x + y + 60 + y = 409\)	M1	3.1b
\(x = 15\) and \(y = 7\)	A1	2.2a
	(9)
	(11 marks)

AS October 2020 Q3

EdexcelAS paperCurrent spec11 marksMinimum Spanning Trees Route Inspection

Figure 2: network on vertices A to H with arcs AB 2x + 10, AD 3x – 2, BC 30, BD 20, BG 25, CE 42, CG 15, DG 8, DH 7, EF 12, EG 23, FG 10, FH 29, GH 17 — Figure 2

[The weight of the network is \(5x + 246\)]

(a) Explain why it is not possible to draw a graph with an odd number of vertices of odd valency. (2)

Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road.

Prim’s algorithm, starting at A, is applied to the network. The order in which the arcs are selected is AD, DH, DG, FG, EF, CG, BD. It is given that the order in which the arcs are selected is unique.

(b) Using this information, find the smallest possible range of values for \(x\), showing your working clearly. (3)

A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex.

Given that the time taken to traverse this route is 318 minutes,

Mark scheme (a)

Scheme	Marks	AO
e.g. (each arc contributes 1 to the orders of two nodes, and so) the sum of the orders of all the nodes is equal to twice the number of arcs	B1	1.2
Which implies that the sum of the orders of all the nodes is even and therefore there must be an even (or zero) number of vertices of odd order hence there cannot be an odd number of vertices of odd order	B1dep	2.4
	(2)

Notes

B1: For one of the following points:

‘Sum of the order/valencies of the nodes/vertices = 2(number of arcs/edges)’
‘Each arc/edge contributes 1 to the order/valency of two nodes/vertices’
‘Sum of the order/valencies of the nodes/vertices is even’

But condone for B1 only

‘sum of the valencies = 2(number of arcs/edges)’ or ‘sum of the nodes/vertices = 2(number of arcs/edges)’ or ‘sum of the orders = 2(number of arcs/edges)
‘sum of the valencies is even’ or ‘sum of the nodes/edges is even’

B1dep: Stating that ‘the sum of the order (or valencies) of the nodes/vertices = 2(number of arcs/edges) therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order) OR each arc/edge contributes 1 to the order of two nodes/vertices therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order)

So in summary the first B mark should be awarded for a broadly correct statement (but allow bod as shown in the last two bullet-points above) but for both B marks a fully correct explanation must be given without any bod (please note therefore it is not possible to score B0B1). Do not accept non-technical language for nodes/arcs for either B1B0 or B1B1

Mark scheme (b)

Scheme	Marks	AO
Either \(2x + 10 > 3x - 2\) or \(2x + 10 > 20\)	M1	3.1b
\(x < 12\)	A1	1.1b
\(x > 5\)	A1	1.1b
	(3)

Notes

M1: Either comparing arc AB with AD or BD with AB – accept any inequality symbol or equals

A1: CAO (\(x < 12\))

A1: CAO (\(x > 5\))

Mark scheme (c)

Scheme	Marks	AO
Applies the route inspection algorithm to this non-standard case	M1	3.1b
C(GF)E + F(GD)H = 37 + 25 = 62	A1	1.1b
C(G)F + E(FGD)H = 25 + 37 = 62	A1	1.1b
C(GD)H + EF = 30 + 12 = 42*	A1	1.1b
\(5x + 246 + 42 = 318\)	M1dep	3.1a
\(x = 6\)	A1	2.2a
	(6)
	(11 marks)

Notes

M1: Correct three pairings of the required four odd nodes (C, E, F and H)

A1: Any one correct pairing and total

A1: Any two correct pairings and totals

A1: All three correct pairings and totals

M1dep: Setting up an equation using the given values and their smallest pairing (dependent on the previous M mark) – must have three totals from application of route inspection

A1: CAO (\(x = 6\))

AS June 2019 Q4

EdexcelAS paperCurrent spec10 marksRoute Inspection Shortest Path

Figure 1: network on vertices A to H with arcs AB 10, AC 17, AD 9, BC 5, BE 25, CD 7, CE x + y, CF 7, CG 3, DG 12, EF 16, EH 9, FG 2, FH 13, GH 3x + y — Figure 1

[The total weight of the network is \(135 + 4x + 2y\)]

The weights on the arcs in Figure 1 represent distances. The weights on the arcs CE and GH are given in terms of \(x\) and \(y\), where \(x\) and \(y\) are positive constants and \(7 < x + y < 20\)

There are three paths from A to H that have the same minimum length.

(a) Use Dijkstra’s algorithm to find \(x\) and \(y\). (7)

An inspection route starting at A and finishing at H is found. The route traverses each arc at least once and is of minimum length.

(b) State the arcs that are traversed twice. (1)

(d) Determine the length of the inspection route. (1)

Dijkstra labelling: A 1 0; D 2 9; B 3 10; C 4 15 (17 16 15); G 5 18 (21 18); F 6 20 (22 20); E 7 15 + x + y (35, 15 + x + y); H 8 33 (18 + 3x + y, 33, 24 + x + y) — Mark scheme (a)

Scheme	Marks	AO
	M1 A1 A1ft A1	1.1b 1.1b 1.1b 1.1b
Attempt to form a pair of simultaneous equations using their three working values from H e.g. \(3x + y = 15\) or \(x + y = 9\) \(x = 3,\ y = 6\)	M1dep A1 A1	3.1a 2.1 2.2a
	(7)

Scheme	Marks	AO
Arcs BC and CD need to be traversed twice	B1	1.1b
	(1)

Scheme	Marks	AO
Vertex C would appear 4 times	B1	2.2a
	(1)

Mark scheme (d)

Scheme	Marks	AO
135 + 4(3) + 2(6) + 12 = 171	B1ft	1.1b
	(1)
	(10 marks)

Notes

B1ft: Follow through only for \(135 + 12 + 4x + 2y\) (for their \(x\) and \(y\) values provided \(7 < x + y < 20\) and \(x\) and \(y\) are positive constants)

A2 June 2019 Q2

EdexcelCurrent spec14 marksRoute Inspection Shortest Path

Figure 1: network on A to J with arcs AB 38, AC 75, AF 42, BD 42, BE 15, CF 20, CG 7, DJ 10, EG 10, EJ 17, FG 12, FH 39, GJ 14, GH 23, HJ 6 — Figure 1

[The total weight of the network is 370]

Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.

(a) Use Dijkstra’s algorithm to find the shortest path from A to D, stating the path and its length. (6)

On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G.

(b) Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear. (4)

On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B.

(d)

(i) Determine the possible starting and finishing points so that the length of Naasir’s route is minimised. You must give reasons for your answer.

(ii) Find the length of Naasir’s new route. (3)

Dijkstra labelling from A: A 1 0 (0); B 2 38 (38); F 3 42 (42); E 4 53 (53); G 5 54 (54 63); C 6 61 (75 62 61); J 7 68 (70 68); H 8 74 (81 77 74); D 9 78 (80 78) — Mark scheme (a)

Mark scheme (b)

Scheme	Marks	AO
A(FG)C + E(J)H = 61 + 23 = 84 A(B)E + C(GJ)H = 53 + 27 = 80* A(FGJ)H + C(G)E = 74 + 17 = 91	M1 A1ft A1	3.1b 1.1b 1.1b
Repeat arcs: AB, BE, CG, GJ and JH	A1	2.2a
	(4)

Notes

(b) M1: correct three pairings of the correct four odd nodes (A, C, E and H)

A1ft: any row correct including pairing and total (ft the final values from (a) for their shortest paths from A to the three other nodes C, E or H only (so the pairing that does not include A must be correct))

A1: all three rows correct including pairings and totals

A1: selecting the shortest pairing, and stating that these arcs (AB, BE, CG, GJ and JH) should be repeated. Must be these arcs and not e.g. ABE, CGJH or AE via B, etc.

Mark scheme (c)

Scheme	Marks	AO
Length of the route is 370 + 80 = 450 metres	B1ft	2.2a
	(1)

Notes

(c) B1ft: For 370 + their smallest repeat out of a choice of at least two totals seen in (b) – this mark is dependent on M1 in (b)

Mark scheme (d)

Scheme	Marks	AO
(i) If node B is removed this makes D, C, G and H odd	M1	3.1b
The shortest path between any two odd nodes is CG (so repeat CG) so the route should start at D and finish at H (or vice-versa)	A1	2.2a
(ii) Length of new route is 370 – 38 – 42 – 15 + 7 = 282 metres	B1	2.2a
	(3)
	(14 marks)

Notes

(d) M1: Mention of the fact that these four nodes D, C, G and H only are now odd or clear consideration of these four nodes only

A1: CAO D and H and must have clearly indicated that the shortest path is from C to G (or vice-versa) – but A0 if clearly selecting the shortest pairing first before selecting the shortest path (as the shortest path is embedded in the shortest pairing)

B1: CAO (282)

D1 June 2019 Q2

EdexcelOld spec11 marksRoute Inspection

Figure 3: weighted network of roads on nodes A, B, C, D, E, F, G, H, J — Figure 3

[The total weight of the network is 48.2]

A surveyor needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Figure 3. The number on each arc represents the length of that road in miles. To check all the roads, she needs to travel along each road at least once. She wishes to minimise the total distance travelled.

The surveyor’s office is at F, so she starts and ends her journey at F.

(a) Find a route for the surveyor to follow. State your route and its length. You must make your method and reasoning clear. (4)

The surveyor lives at D and wonders if she can reduce the distance travelled by starting from home and inspecting all the roads on the way to her office at F.

(b) By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in the inspection route from D to F. You must make your method and working clear. (5)

(c) Determine which of the two routes, the one starting at F and ending at F, or the one starting at D and ending at F, is longer. You must show your working. (2)

Mark scheme (a)

Scheme	Marks
Pair the two odds nodes: A with H	B1
Repeat arcs AG, GJ, JH	B1
Length = 48.2 + (2.5 + 0.9 + 1.1) = 48.2 + 4.5 = 52.7	B1
e.g. route FAGABFGJGHJHFEJBCDECF	B1
	(4)

Notes

a1B1: CAO (correct pairing of the two odd nodes stated) – this mark may be implied by consideration of the shortest path from A to H (or vice-versa)

a2B1: Correct repeated arcs stated (AG, GJ, JH)

a3B1: CAO (length of 52.7)

a4B1: Correct route: checks – starts and finishes at F, 21 nodes, AG, GJ and JH repeated, A(2), B(2), C(2), D(1), E(2), F(4), G(3), H(2), J(3)

Mark scheme (b)

Scheme	Marks
AD + FH = A(BC)D + F(GJ)H = 6 + 3.7 = 9.7	M1 A1
AF + DH = AF + D(EJ)H = 2.4 + 5.5 = 7.9*	A1
AH + DF = A(GJ)H + D(E)F = 4.5 + 3.8 = 8.3	A1
Repeat arcs AF, DE, EJ and JH	A1
	(5)

Notes

b1M1: Three distinct pairings of nodes A, D, F and H

b1A1: Any one row correct including pairing and total

b2A1: Any two rows correct including pairings and totals

b3A1: All three rows correct including pairings and totals

b4A1: CAO correct arcs clearly (not just in their working) stated: AF, DE, EJ and JH. Do not accept DH, DEJH or DH via E and J

Mark scheme (c)

Scheme	Marks
Route from D to F is longer	B1
Difference = (48.2 + 7.9) – 52.7 = 3.4 or 7.9 – 4.5 = 3.4	B1
	(2)
	11 marks

Notes

c1B1: CAO (oe e.g. F to F is shorter) – dependent on correct repeats in (a) and (b) or clearly implied in (c) (e.g. correct values compared in this part)

c2B1: CAO (difference of 3.4 or comparing 52.7 and 56.1 or comparing 7.9 with 4.5)

D1 June 2018 Q4

EdexcelOld spec14 marksRoute Inspection Shortest Path

Figure 2: weighted network of roads with vertices A to J — Figure 2

[The total weight of the network is 293]

Figure 2 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along the corresponding road.

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

The road represented by edge GJ is closed due to essential maintenance. Sahil needs to travel along all the other roads to check that they are in good repair. Sahil wishes to complete his route as quickly as possible and will start and finish at the same vertex.

(b) Use the route inspection algorithm to find the duration of Sahil’s quickest route. State the edges that will need to be traversed twice. You should make your method and working clear. (6)

Given that Sahil will start and finish at vertex C,

Dijkstra labelling: A 1 0; B 2 17; F 3 32; E 4 40; C 5 46; D 6 56; G 7 60; H 8 65; J 9 69 — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
A(BFE)C + D(C)E = 46+ 16 = 62	M1 A1
A(BFEC)D + CE = 56 + 6 = 62	A1
A(BF)E + CD = 40 + 10 = 50*	A1
Repeat edges: AB, BF, EF and CD	A1
Duration = 293 – 10 + 50 = 333 (minutes)	A1
	(6)

Notes

b1M1: Three distinct pairings of A, C, D and E

b1A1: Any row correct including pairing and total

b2A1: Any two rows correct including pairings and totals

b3A1: All three rows correct including pairings and totals

b4A1: CAO correct edges clearly stated (and not just in their working) as AB, BF, EF, CD. Do not accept AE, ABFE or AE via B and F

b5A1: CAO (333)

Mark scheme (c)

Scheme	Marks
Vertex E: 3 Vertex F: 3	B1 B1
	(2)
	(14 marks)

Notes

c1B1: CAO (vertex E)

c2B1: CAO (vertex F)

In (c) if answer lines not used then:

3, 3	B1 B1
3 + 3 = 6	B1 B1
3, \(x\) where \(x \ne 3\)	B1 B0
\(x\), 3 where \(x \ne 3\)	B0 B1
3	B1 B1
6	B0 B0

If after (b) a 3 appears only and it is not labelled as (c) then award no marks

D1 June 2017 Q4

EdexcelOld spec15 marksRoute Inspection Shortest Path

Figure 4: weighted network of roads with vertices A to J — Figure 4

[The total weight of the network is 85]

Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn wishes to travel from A to H. She wishes to minimise the distance she travels.

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

On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.

(b) Use the route inspection algorithm to find the length of the shortest inspection route. State the edges that should be repeated. You should make your method and working clear. (5)

The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A.

(c)

(i) State the edges that should be repeated.

(ii) State a possible route and calculate its length. You must make your method and working clear. (4)

Dijkstra labelling: A 1 0; D 2 5; C 3 9; B 4 10; E 5 12; F 6 13; G 7 17; J 8 18; H 9 20 — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
AD + E(F)G = 5 + 5 = 10* A(DCB)E + D(CBEF)G = 12 + 12 = 24 A(DCBEF)G + D(CB)E = 17 + 7 = 24	M1 A1 A1
Repeat edges: AD, EF, FG	A1
Length = 85 + 10 = 95 (miles)	A1ft
	(5)

Notes

b1M1: Three distinct pairings of A, D, E and G

b1A1: Any two rows correct including pairings and totals

b2A1: All three rows correct including pairings and totals

b3A1: CAO correct edges clearly (not just in their working) stated as AD, EF, FG. Do not accept EG, EFG or or EG via F

b4A1ft: 85 + their smallest repeat out of a choice of at least two totals seen (the correct answer of 95 must come from the correct pairing of AD and EG)

Mark scheme (c)

Scheme	Marks
(i) AD, CD, BC, BG	B1
(ii) Route: e.g. ADABCDCBFEHJFGBGA	B1
Length = 85 + 18 – 6 – 2 = 95 (miles)	M1 A1
	(4)
	(15 marks)

Notes

c1B1: CAO (AD, CD, BC, BG)

c2B1: Any correct route (the route may be given in terms of either vertices (ADA…) or arcs (AD, DA, AB,…)) – checks: start and finish at A, 17 vertices (repeats AD, CD, BC, BG, and nodes A, B appear three times, C, D, F, G appear twice and E, H and J appear once)

c1M1: 85 – 6 – 2 + ‘18’ (where ‘18’ is the sum of their repeated arcs from A to G in c1B1 (this may need to be checked) or a clear attempt at their shortest path from A to G) or 85 – 8 + ‘18’ or 95 or for adding the weights of all the arcs from their route (so ft their answers from c1B1 and c2B1)

c1A1: CAO of 95 including as a minimum the working 85 + 18 – 8 or explicitly adding the weights of all the arcs from a correct route given in c2B1. Note that 85 + 10 or 77 + 18 alone is not sufficient for this mark (ignore units)

D1 June 2016 Q6

EdexcelOld spec11 marksRoute Inspection

Figure 5: weighted network of corridors with vertices A to L — Figure 5

[The total weight of the network is 384]

Figure 5 models a network of corridors in an office complex that need to be inspected by a security guard. The number on each arc is the length, in metres, of the corresponding section of corridor.

Each corridor must be traversed at least once and the length of the inspection route must be minimised. The guard must start and finish at vertex A.

(a) Use the route inspection algorithm to find the length of the shortest inspection route. State the arcs that should be repeated. You should make your method and working clear. (5)

It is now possible for the guard to start at one vertex and finish at a different vertex. An inspection route that traverses each corridor at least once is still required.

(b) Explain why the inspection route should start at a vertex with odd degree. (2)

The guard decides to start the inspection route at F and the length of the inspection route must still be minimised.

(d) State a possible route and its length. (2)

Mark scheme (a)

Scheme	Marks
B(AD)E + F(J)H = 45 + 30 = 75*	M1
B(CK)F + E(DG)H = 50 + 35 = 85	A1 (2 correct)
B(CKJ)H + E(DGHJ)F = 60 + 65 =125	A1 (3 correct)
Arcs BA, AD, DE, FJ and JH will be traversed twice	A1
Route length = 384 + 75 = 459 (metres)	A1ft
	(5)

Notes

a1M1: Three distinct pairings of the correct four odd nodes

a1A1: Any two rows correct including pairings and totals

a2A1: All three rows correct including pairings and totals

a3A1: CAO correct arcs clearly (not just in their working) stated: BA, AD, DE, FJ, JH. Accept BADE, FJH or BE via A and D, FH via J. Do not accept BE, FH

a4A1ft: Correct answer of 459, or 384 + their smallest repeat out of a choice of at least two totals seen

Mark scheme (b)

Scheme	Marks
e.g. if we start at an odd vertex we will finish at another odd vertex. This removes the need to repeat the route between them. So we just have to consider one repeated route rather than two	B2, 1, 0
	(2)

Notes

b1B1: One of (i) finishing at an odd vertex (ii) only having to repeat one route/pairing/pair/path (but not ‘repeat only one arc’) rather than two or having one less route/pairing/pair/path to repeat (but not an argument based only on arcs e.g. ‘one less arc to repeat’ or ‘it reduces the number of arcs’)

b2B1: Correct complete argument – including both (i) and (ii) from b1B1 (so B0B1 is not possible in (b))

Mark scheme (c)

Scheme	Marks
We only have to repeat one pair of odd vertices which does not include F (BE = 45, EH = 35, BH = 60)	M1
EH is the smallest of the repeat so repeat EH (ED, DG, GH) and therefore the guard should finish at B	A1
	(2)

Notes

c1M1: Identifies the need to repeat one route of BE(45), EH(35), BH(60), which does not include F (maybe implicit) or a general comment to repeat one route that does not include F

c1A1: Identifies EH (but not just 35) as the least of those paths not including F, and B as the position of the finishing vertex. Note that they must either explicitly state that EH is the least not including F (just stating that EH is the least is A0) or they list the three pairings (BE, EH, BH) and only these three pairings in this part and state that EH is the least

Mark scheme (d)

Scheme	Marks
Route e.g. FJKFCKLJHGHEDGDECBDAB	B1
The length of the route is 419 (metres)	B1ft
	(2)
	(11 marks)

Notes

d1B1: Any correct route – checks: start at F and finishes at B, 21 vertices (repeats ED, DG, GH, and node A appears 1, B(2), C(2), D(3), E(2), F(2), G(2), H(2), J(2), K(2), L(1))

d2B1ft: Correct answer of 419 or 384 + their EH (i.e. the least route that does not include F – so their smallest of BE, EH, BH – must be their smallest value (usually from (a)) not what they state/think is their smallest value). This mark is dependent on the M mark in (a)

D1 June 2015 Q4

EdexcelOld spec12 marksRoute Inspection

Figure 4: weighted network of roads with vertices A to H — Figure 4

[The total weight of the network is 2090]

(a) Explain why a network cannot have an odd number of vertices of odd valency. (2)

Figure 4 represents a network of 13 roads in a village. The number on each arc is the length, in metres, of the corresponding road. A route of minimum length that traverses each road at least once needs to be found. The route may start at any vertex and finish at any vertex.

(b) Write down the vertices at which the route will start and finish. (1)

A new road, AB, of length 130m is built. A route of minimum length that traverses each road, including AB, needs to be found. The route must start and finish at A.

(c) Use the route inspection algorithm to find the roads that will need to be traversed twice. You must make your method and working clear. (4)

(d) Calculate the length of a possible shortest inspection route. (2)

It is now decided to start and finish the inspection route at two distinct vertices. A route of minimum length that traverses each road, including AB, needs to be found. The route must start at A.

(e) State the finishing point so that the length of the route is minimised. Calculate how much shorter the length of this route is compared to the length of the route in (d). You must make your method and calculations clear. (3)

Mark scheme (a)

Scheme	Marks
e.g. (each arc contributes 1 to the orders of two nodes, and so) the sum of the orders of all the nodes is equal to twice the number of arcs	B1
Which implies that the sum of the orders of all the nodes is even and therefore there must be an even (or zero) number of vertices of odd order hence there cannot be an odd number of vertices of odd order.	B1
	(2)

Notes

a1B1: Either stating that the sum of the order of the nodes = 2(number of arcs) or that each arc contributes 1 to the order of two nodes. For this mark there must be a clear correct statement linking the order of nodes to arcs

a2B1: For stating that as the sum (of the orders) of the nodes is even this implies that there must be an even number of nodes of odd order (or there cannot be an odd number of nodes of odd order). Candidates may argue that if the sum (of the order) of the nodes is odd then this implies that the number of arcs cannot be integer valued (oe) which is fine. For this mark there must be a correct statement that the sum of the nodes is even together with the correct conclusion. Note that for the first B mark it must be clear that the candidate is considering the order of the nodes but for the second B mark it is sufficient to for candidates to say ‘the sum of the nodes…’. Furthermore, it is possible to score B0B1 (for example, a candidate may simply state the sum of the nodes is even and state the correct conclusion which would score the 2nd B mark only)

Mark scheme (c)

Scheme	Marks
A(C)B + D(BC)E = 120 + 300 = 420	M1
A(CB)D + B(C)E = 290 + 130 = 420	A1 (2 rows)
A(C)E + BD = 150 + 170 = 320*	A1 (3 rows)
Repeat arcs AC, CE and BD	A1
	(4)

Notes

c1M1: Three distinct pairings of the correct four odd nodes

c1A1: Any two rows correct including pairings and totals

c2A1: All three rows correct including pairings and totals

c3A1: CAO correct arcs clearly (not just in their working) stated: AC, CE, BD. Accept ACE or AE via C. Do not accept AE

Mark scheme (d)

Scheme	Marks
Length 2090 + 320 + 130 = 2540 (m)	M1, A1
	(2)

Notes

d1M1: 2090 + 130 + (their smallest total from (c)); must be at least two distinct pairings of the correct four odd nodes in (c) or for 2410 only (forgetting to add the additional 130)

d1A1: CAO (2540) – if no working seen then the correct answer implies both marks in (d)

Mark scheme (e)

Scheme	Marks
(Finishing Point is) D	B1
Difference in routes = 2540 – (2090 + 130 +130 ) = 190 (m)	M1, A1
	(3)
	(12 marks)

Notes

e1B1: CAO (D)

e1M1: Their answer to (d) – (2090 + 130 + their BE) (if AB included in (d)) or their answer to (d) – (2090 + their BE) (if AB not included in (d)) or (their smallest total (320) from (c) – their BE (130)) – by ‘their BE’ this is their smallest pairing which does not include A. This mark is dependent on either scoring the M mark in (c) or considering all three pairings (DE, BE, BD) that do not include A

e1A1: CAO (190) – condone lack of units – if the correct answer is seen with no calculation and/or method seen then award the M mark only. Candidates who did not include AB (130) in their inspection route (in (d)) can still earn full marks in (e) for the correct answer of 190

D1 June 2014 (R) Q4

EdexcelOld spec13 marksRoute Inspection

Figure 4: weighted network with vertices A to I — Figure 4

[The total weight of the network is 359 cm]

Figure 4 represents the network of sensor wires used in a medical scanner. The number on each arc represents the length, in cm, of that section of wire.

After production, each scanner is tested.

A machine will be programmed to inspect each section of wire.

It will travel along each arc of the network at least once, starting and finishing at A. Its route must be of minimum length.

(a) Use the route inspection algorithm to find the length of a shortest inspection route. You must make your method and working clear. (5)

The machine will inspect 15 cm of wire per second.

(b) Calculate the total time taken, in seconds, to test 120 scanners. (2)

It is now possible for the machine to start at one vertex and finish at a different vertex. An inspection route of minimum length is still required.

Due to constraints at the factory, only B or D can be chosen as the starting point and there will also be a 2 second pause between tests.

(d) Determine the new minimum total time now taken to test 120 scanners. You must state which vertex you are starting from and make your calculations clear. (4)

Mark scheme (a)

Scheme	Marks
B(E)D + FI = 32 + 38 = 70	M1 A1
B(C)F + D(E)I = 25 + 36 = 61*	A1
B(E)I + D(E)F = 20 + 52 = 72	A1
Length = 359 + 61 = 420	A1ft
	(5)

Notes

a1M1: Three pairings of the correct four odd nodes.

a1A1: One row correct including pairing and total.

a2A1: Two rows correct including pairing and total.

a3A1: Three rows correct including pairing and total.

a4A1ft: 420 or 359 + their least.

Mark scheme (c)

Scheme	Marks
e.g. If we start at an odd vertex we will finish at another odd vertex. This removes the need to repeat the route between them. So we just have to consider one repeated route rather than two.	B2,1,0
	(2)

Notes

c1B1: One of (i) idea of finishing at an odd vertex (ii) only having to repeat one route rather than two.

c2B1: Correct complete argument – including both (i) and (ii) from c1B1.

Mark scheme (d)

Scheme	Marks
Choose to repeat the shortest route BI (20)	B1
Therefore start at D (and finish at F)	B1
New length = 359 + 20 = 379	B1
Time taken \(= \dfrac{379}{15} \times 120 + 2 \times 119 = 3270\) (seconds)	B1
	(4)
	(13 marks)

Notes

d1B1: Identifies BI as the shortest route.

d2B1: start at D – dependent on identifying BI (20) as the repeat.

d3B1: CAO

d4B1: CAO

D1 June 2014 Q3

EdexcelOld spec10 marksRoute Inspection

Figure 1: network of forest tracks A to M with lengths in km — Figure 1

[The total weight of the network is 451]

Figure 1 models a network of tracks in a forest that need to be inspected by a park ranger. The number on each arc is the length, in km, of that section of the forest track.

Each track must be traversed at least once and the length of the inspection route must be minimised. The inspection route taken by the ranger must start and end at vertex A.

(a) Use the route inspection algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear. (5)

(b) State the number of times that vertex J would appear in the inspection route. (1)

The landowner decides to build two huts, one hut at vertex K and the other hut at a different vertex. In future, the ranger will be able to start his inspection route at one hut and finish at the other. The inspection route must still traverse each track at least once.

(c) Determine where the other hut should be built so that the length of the route is minimised. You must give reasons for your answer and state a possible route and its length. (4)

Mark scheme (a)

Scheme	Marks
D(A)E + F(J)K = 35 + 15 = 50* D(HJ)F + E(FJ)K = 24 + 40 = 64 D(HJ)K + EF = 33 + 25 = 58	M1 A1 (2 correct) A1 (3 correct)
Arcs DA, AE, FJ, JK will be traversed twice	A1
Route length = 451 + 50 = 501 (km)	A1ft
	(5)

Notes

a1M1 Three distinct pairings of the correct four odd nodes.

a1A1 Any two rows correct including pairings and totals.

a2A1 All three rows correct including pairings and totals.

a3A1 CAO correct arcs clearly (not just in their working) stated: DA, AE, FJ, JK. Accept DAE, FJK or DE via A, FK via J. Do not accept DE, FK.

a4A1ft The correct answer of 501 or 451 + their smallest repeat out of a choice of at least two totals seen.

Mark scheme (c)

Scheme	Marks
We only have to repeat one pair of odd vertices which does not include vertex K (DE = 35, DF = 24, EF = 25)	M1
DF is the smallest of the three so repeat DF (DH, HJ, JF) and therefore the other hut should be built at E	A1
Route e.g. EADEHDHJFBEFCGFJHLGKJLMK	A1
The length of the route is 475 (km)	A1ft
	(4)
	(10 marks)

Notes

c1M1 Identifies the need to repeat one pairing not including K (maybe implicit) or listing of possible repeats – this mark is dependent on scoring the M mark in (a). Stating any pairing that does not include K is sufficient for this mark.

c1A1 Identifies DF as the least of those pairings not including K and E as the position of the other hut. They have to explicitly state that DF is the least pairing that does not include K or they can list all three pairings (DE, DF, EF) and then say DF is the smallest as this implicitly implies that they are considering only pairings that do not include K.

c2A1 Any correct route (checks: starts at E and finishes at K (or vice-versa), 24 vertices (D, G, L appear twice and E, F, H, J appear three times and every other letter appears at least once).

c3A1ft Correct answer of 475 or 451+ their DF (i.e. the least pairing that does not include K – so their smallest of DE, DF or EF).

D1 June 2013 (R) Q5

EdexcelOld spec10 marksRoute Inspection

Figure 4: network of power cables A to H — Figure 4

[The total weight of the network is 181 miles]

Figure 4 represents a network of power cables that have to be inspected. The number on each arc represents the length, in km, of that cable.

A route of minimum length that traverses each cable at least once and starts and finishes at A needs to be found.

(a) Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear. (5)

(b) Write down a possible shortest inspection route, giving its length. (2)

It is now decided to start and finish the inspection route at two distinct vertices. The route must still traverse each cable at least once.

(c) Determine possible starting and finishing points so that the length of the route is minimised. You must give reasons for your answer. (3)

Mark scheme (a)

Scheme	Marks
AF + GH = 15 + 31 = 46*	M1
AG + FH = 32 + 15 = 47 AH + FG = 30 + 17 = 47	A3,2,1.0
so repeat arcs AB, BF and GH	A1
	(5)

Notes

a1M1 Three distinct pairings of their four odd nodes

a1A1 Any one row correct including pairing and total

a2A1 Any two rows correct including pairing and total

a3A1 All three rows correct including pairing and total

a4A1 CAO correct arcs identified AB, BF and GH. Accept ABF or AF via B (check to see if via B appears in working) but do not accept AF for this mark

Mark scheme (b)

Scheme	Marks
E.g. ABCDBFDEHGFHGAFBA (17 nodes)	B1
length = 181 + 46 = 227	B1 ft
	(2)

Notes

b1B1 Any correct route (checks: 17 nodes, the route starts and ends at A, pairings AB, BF and GH appear twice in the route and every letter from A to H (inclusive) appears at least once).

b2B1ft correct answer of 227 or 181 + their least out of a choice of at least two totals given in part (a)

Mark scheme (c)

Scheme	Marks
One path will have to be repeated. The shortest is 15	M1
So repeat AF, use G and H as the start and finish. or repeat FH, use A and G as the start and finish.	A1A1
	(3)
	(10 marks)

Notes

c1M1 Identifies need to repeat one pairing (maybe implicit) and 15 (or either AF or FH) specifically identified as the least

c1A1 Repeat (either AF or FH) identified clearly

c2A1 G and either A or H identified as start and finish.

D1 June 2013 Q5

EdexcelOld spec10 marksRoute Inspection

Figure 4: railway network A to H with lengths in miles — Figure 4

[The total weight of the network is 344 miles]

Figure 4 represents a railway network. The number on each arc represents the length, in miles, of that section of the railway.

Sophie needs to travel along each section to check that it is in good condition.

She must travel along each arc of the network at least once, and wants to find a route of minimum length. She will start and finish at A.

(a) Use the route inspection algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear. (5)

(b) Write down a possible shortest inspection route, giving its length. (2)

Sophie now decides to start the inspection route at E. The route must still traverse each arc at least once but may finish at any vertex.

(c) Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route. (3)

Mark scheme (a)

Scheme	Marks
AB + DE = 44 + 30 = 74*	M1
AD + BE = 42 + 35 = 77 AE + BD = 39 + 38 = 77	A3.2.1.0
Repeat arcs AC, BC and DE	A1
	(5)

Notes

a1M1 Three distinct pairings of their four odd nodes

a1A1 Any one row correct including pairing and total

a2A1 Any two rows correct including pairing and total

a3A1 All three rows correct including pairing and total

a4A1 CAO correct arcs identified AC, BC and DE. Accept ACB or AB via C (check to see if via C appears in working) but do not accept AB for this mark

Mark scheme (b)

Scheme	Marks
E.g. ABCADCBEDFGDEGHECA (18 nodes)	B1
Length: 344 + 74 = 418	B1ft
	(2)

Notes

b1B1 Any correct route (checks: eighteen nodes (or seventeen arcs), the route starts and ends at A, pairings AC, BC and DE appear twice in the route and that every letter (A to H inclusive) appears at least once).

b2B1ft correct answer of 418 or 344 + their least out of a choice of at least two totals given in part (a)

Mark scheme (c)

Scheme	Marks
One of AB (44), AD (42) or BD (38) will still have to be repeated.	M1
BD(38) is the shortest	A1
So start at E and finish at A, route length now is 344 + 38 = 382	DA1
	(3)
	(10 marks)

Notes

c1M1 Either identifies the need to repeat one pairing which does not include E (could list potential repeats) or identifies the need to repeat BD (or 38).

c1A1 Identifies the need to repeat one pairing which does not include E and this is BD (38) because it is the least. To score the first two marks the candidate must make it clear that they need to repeat BD because it has the least weight of those pairings that do not include E.

c2DA1 correct finishing point (A) and length (382). This mark is dependent on them identifying BD (38) as the repeat.

D1 January 2013 Q5

EdexcelOld spec15 marksMinimum Spanning Trees Route Inspection

Figure 5: network of roads A to J with lengths in km — Figure 5

[The weight of the network is 379]

Figure 5 represents the roads in a highland wildlife conservation park. The vertices represent warden stations. The number on each arc gives the length, in km, of the corresponding road.

During the winter months the park is closed. It is only necessary to ensure road access to the warden stations.

(a) Use Prim’s algorithm, starting at A, to find a minimum connector for the network in Figure 5. You must state the order in which you include the arcs. (3)

(b) Given that it costs £80 per km to keep the selected roads open in winter, calculate the minimum cost of ensuring road access to all the warden stations. (2)

At the end of winter, Ben inspects all the roads before the park re-opens. He needs to travel along each road at least once. He will start and finish at A, and wishes to minimise the length of his route.

(c) Use the route inspection algorithm to find the roads that will be traversed twice. You must make your method and working clear. (6)

(d) Find the length of the shortest inspection route. (1)

If Ben starts and finishes his inspection route at different warden stations, a shorter inspection route is possible.

(e) Determine the two warden stations Ben should choose as his starting and finishing points in order that his route has minimum length. Give a reason for your answer and state the length of the route. (3)

Mark scheme (a)

Scheme	Marks
AC (32) CF (14) DF (12) EF (17); BE (15) FI(18); IJ (10) GJ (9) DH (19)	M1 A1; A1
	(3)

Notes

Accept the weight of each arc to represent the arcs (as each value is unique).

a1M1 First four arcs correctly chosen or first five nodes correctly chosen (A, C, F, D, E, …). Any rejections seen during selection scores M0. Order of nodes may be seen at the top of a matrix.

a1A1 First six arcs correctly chosen or all nodes correctly chosen (A, C, F, D, E, B, I, J, G, H). Order of nodes may be seen at the top of a matrix.

a2A1 CSO (must be considering arcs for this final mark).

Misread in (a): Starting at a node other than A scores M1 only – must have the first four arcs (or five nodes or numbers) correct.

Starting at	Minimum Arcs required for M1 only	Nodes	Order
B	BE,EF,DF,CF	B, E, F, D, C	(10)15423(8967)
C	CF,DF,EF,BE	C, F, D, E, B	(10)51342(8967)
D	DF,CF,EF,BE	D, F, C, E, B	(10)53142(8967)
E	BE,EF,DF,CF	E, B, F, D, C	(10)25413(8967)
F	DF,CF,EF,BE	F, D, C, E, B	(10)53241(8967)
G	GJ,IJ,FI,DF	G, J, I, F, D	(10)(86)5(7)41(9)32
H	DH,DF,CF,EF	H, D, F, C, E	(10)(6)4253(9)1(78)
I	IJ,GJ,FI,DF	I, J, G, F, D	(10)(86)5(7)43(9)12
J	GJ,IJ,FI,DF	J, G, I, F, D	(10)(86)5(7)42(9)31

Mark scheme (b)

Scheme	Marks
\(146 \times 80 =\) (£) 11 680	M1 A1
	(2)

Notes

b1M1 \(80 \times\) their MST weight. Accept a value in the interval \([114, 178] \times 80\) for this mark. If no working is seen then M0 unless answer is correct.

b1A1 CAO (11680 with no working scores both marks).

Mark scheme (c)

Scheme	Marks
BF + GH = 32 + 40 = 72 BG + FH = 39 + 25 = 64* BH + FG = 57 + 37 = 94	M1 A3,2,1,0
Roads BE, EG and FH need repeating	A1ft A1
	(6)

Notes

c1M1 Three distinct pairings of their four odd nodes.

c1A1 Any one row correct including pairing and total.

c2A1 Any two rows correct including pairing and total.

c3A1 All three rows correct including pairing and total.

c4A1ft Their smallest arcs repeated (e.g. accept BEG or BG via E but not just BG). BEG (or e.g. BG via E) could appear in their working.

c5A1 CAO BE, EG and FH. Accept BEG or BG via E (could appear in working) but not just BG.

Mark scheme (e)

Scheme	Marks
Ben should choose to repeat FH (25) since this is the shortest.	M1
He should choose B and G as his start and finish vertices	A1
Route length is 379 + 25 = 404 (km)	A1
	(3)
	(15 marks)

Notes

e1M1 FH (or 25) specifically identified as least.

e1A1 B and G identified as the start and finish nodes.

e2A1 404 CAO (condone lack of (or incorrect) units throughout).

D1 June 2012 Q4

EdexcelOld spec12 marksGraphs & Networks Route Inspection

Figure 3: network of pipes A to K with lengths in metres — Figure 3

[The total weight of the network is 1436 m]

(a) Explain the term valency. (2)

Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe.

Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.

(b) Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear. (5)

Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI. The length of the inspection route must be minimised.

(d) Find the length of the minimum inspection route excluding HI. Justify your answer. (2)

(e) Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI. (2)

Mark scheme (b)

Scheme	Marks
DE + HI = 131 + 75 = 206	M1 1A1
DH + EI = 146 + 137 = 283	2A1
DI + EH = 143 + 62 = 205*	3A1
Arcs EH, DF and FI will be traversed twice.	4A1ft
	(5)

Notes

b1M1 Three pairings of their four odd nodes

b1A1 One row correct including pairing and total

b2A1 Two rows correct including pairing and total

b3A1 Three rows correct including pairing and total

b4A1ft Their smallest repeated arcs, (accept DFI).

Mark scheme (d)

Scheme	Marks
Since HI is removed only D and E are odd, So only the route between DE need to be repeated Route length = 1436 – 75 (for HI) + 131 = 1492(m)	M1 A1
	(2)

Notes

d1M1 Aim to include their DE(131) [ft from (b)] and remove HI(75) or 1436+131–75

d1A1 CAO 1492. Must see method though, NMS gets M0.

Mark scheme (e)

Scheme	Marks
Route should start and finish at D and E. E.g. DCFDAEBGEFKIFHJGHE (18 vertices)	M1, A1
	(2)
	(12 marks)

Notes

e1M1 D and E identified as start and finish nodes. We do not have to see a route here.

e1A1 CAO must see a route. 18 vertices; Each of A–K present; 3E’s, 3F’s, 2D’s, 2G’s and 2H’s.

D1 January 2012 Q2

EdexcelOld spec8 marksRoute Inspection

Figure 2: network with arcs AB 11, AC 10, BC 7, BD 10, CD 6, CE 8, DE 18, DF 10, DG 7, EG 9, FG 8, FH 12, GH 13 — Figure 2

[The weight of the network is 129 miles]

Figure 2 models a network of canals. The number on each arc gives the length, in miles, of that canal.

Brett needs to travel along each canal to check that it is in good repair. He wishes to minimise the length of his route.

(a) Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear. (6)

A canal between B and F, of length 12 miles, is to be opened and needs to be included in Brett’s inspection route.

(b) Determine if the addition of this canal will increase or decrease the length of Brett’s minimum route. You must make your reasoning clear. (2)

Mark scheme (a)

Scheme	Marks
BD + EF = 10 + 17 = 27	M1 A1
BE + DF = 15 + 10 = 25 \(\leftarrow\)	A1
BF + DE = 20 + 14 = 34	A1
Repeat arcs BC, CE and DF	A1ft
Length of route = 129 + 25 = 154	B1ft
	(6)

Notes

a1M1: Three pairings of their four odd nodes

a1A1: One row correct including pairing and total

a2A1: Two rows correct including pairing and total

a3A1: Three rows correct including pairing and total

a4A1ft: Their smallest repeated arcs, (accept BCE).

a1B1ft: 129 + their least out of a choice of at least two possible, distinct, pairings.

Mark scheme (b)

Scheme	Marks
We add BF(12) to the network so only have to repeat DE (14) Length of route is therefore 129 + 12 + 14 = 155	M1
155>154 so his route would be increased	A1
	(2)
	(8 marks)

Notes

b1M1: DE identified, using/repeating 12 + their DE [ft from (a)]

b1A1: CAO, conclusion, numerical argument e.g. ref to 155 or 26 etc.

D1 June 2011 Q5

EdexcelOld spec10 marksRoute Inspection

Figure 5: network with arcs GF 8, GD 5, GE 7, GC 9, FE 3, FB 7, EC 5, EB 5, BC 5, CD 7, CA 9, DA 17, BA 11 — Figure 5

[The total weight of the network is 98 km]

Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe.

A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.

(a) Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear. (5)

(b) Write down a possible shortest inspection route, giving its length. (2)

It is now decided to start the inspection route at D. The route must still traverse each pipe at least once but may finish at any node.

(c) Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route. (3)

Mark scheme (a)

Scheme	Marks
AC + DF = 9 + 13 = 22 \(\leftarrow\)	M1 A1
AD + CF = 16 + 8 = 24	A1
AF + CD = 17 + 7 = 24	A1
Repeat arcs AC, DG and GF	A1ft
	(5)

Notes

(a)M1 Three pairings of their four odd nodes

1A1 One row correct including pairing and total

2A1 Two rows correct including pairing and total

3A1 Three rows correct including pairing and total

4A1ft Their smallest repeated arcs stated accept DGF or arcs clear from selected row.

Mark scheme (b)

Scheme	Marks
E.g. ADCACGDGFGECBEFBA	B1
(Length of route =) 98 + 22 = 120 km	B1ft
	(2)

Notes

(b)1B1 Correct route any start point, 17 nodes, AC, DG and GF repeated

2B1ft CAO 98 + their least out of a choice of at least 2.

Mark scheme (c)

Scheme	Marks
CF (8) is the shortest link between 2 odd nodes excluding D Repeat CF (8) since this is the shortest path excluding D.	M1
We finish at A	A1ft
Length of route = 98 + 8 = 106 (km)	A1ft
	(3)
	(10 marks)

Notes

(c)M1 Attempting just one repeated path excluding D; accept AC, AF and CF listed

1A1ft A and their least repeat [should be CF (CEF)] clearly stating this as least

2A1ft 98 + their least from their working in (a)

D1 January 2011 Q5

EdexcelOld spec11 marksRoute Inspection

Figure 5: network with arcs AB 2.5, AE 2.6, AC 3.2, BD 2.1, DE 1.9, DG 1.9, GI 2.0, EI 3.3, EF 3.2, CF 3.6, FH 3.5, HI 1.8 — Figure 5

[The total weight of the network is 31.6 km]

Figure 5 models a network of roads. The road markings on these roads are to be renewed. The number on each arc represents the length, in km, of that road. In order to renew the road markings, each road must be traversed at least once.

(a) Use the route inspection algorithm, starting and finishing at A, to find a suitable route, which should be stated. You must make your method and working clear. (5)

(b) State the roads that must be traversed twice and the length of the route. (3)

The machine that will be used to renew the road markings can only be delivered to D. It will start at D, but it may finish at any vertex.
Each road must still be traversed at least once.

(c) Given that the route is to be minimised, determine where the machine should finish. Give reasons to justify your answer. (3)

Mark scheme (a)

Scheme	Marks
AD + FI = 4.5 + 5.3 = 9.8	M1 A1
AF + DI = 5.8 + 3.9 = 9.7 smallest	A1
AI + DF = 5.9 + 5.1 = 11.0	A1
e.g. ABDGIGDEIHFEACFEA	A1
	(5)

Notes

1M1: Three pairings of their four odd nodes

1A1: one row correct

2A1: two rows correct

3A1: all correct

4A1: Any correct route (17 nodes)

Mark scheme (b)

Scheme	Marks
Roads AE, EF (or AEF), DG and GI (or DGI) should be repeated.	B1
Length is 31.6 + 9.7 = 41.3 km	M1A1ft
	(3)

Notes

1B1: correct arcs identified

1M1: 31.6 + ft their least, from a choice of at least two.

1A1: ft has correctly their plausible least (from a choice of at least two) to 31.6.

Mark scheme (c)

Scheme	Marks
We now only have to repeat one pair of odd vertices, one of which can not be D. (FI = 5.3, AF = 5.8 and AI = 5.9)	M1
FI gives the smallest of the three so choose to repeat FI (FHI)	A1
The machine should be collected from A.	DA1
	(3)
	(11 marks)

Notes

1M1: Identifies need to repeat one pairing, not including D (maybe implicit) or listing of potential repeats.

1A1: Identifies FI as least.

2DA1: dependent on their identifying FI as repeat

D1 June 2010 Q4

EdexcelOld spec10 marksRoute Inspection

Figure 2: network with arcs AB 5.6, AC 4.8, BE 8.3, BD 6.4, CD 7.6, CF 8.5, ED 4.3, EG 10.1, DG 8.5, FG 9.2 — Figure 2

[The total weight of the network is 73.3 km]

Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km, of that tunnel.
Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route.
He must start and finish at A.

(a) Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear. (5)

(b) Find a route of minimum length, starting and finishing at A.
State the length of your route. (3)

A new tunnel, CG, is under construction. It will be 10 km long.
Malcolm will have to include the new tunnel in his inspection route.

Mark scheme (a)

Scheme	Marks
BC + EG = 10.4 + 10.1 = 20.5 smallest	M1 A1
BE + CG = 8.3 + 16.1 = 24.4	A1
BG + CE = 14.9 + 11.9 = 26.8	A1
So repeat tunnels BA, AC and EG	A1
	(5)

Notes

1M1: Three pairings of their four odd nodes

1A1: one row correct

2A1: two rows correct

3A1: all correct

4A1: correct arcs identified

Mark scheme (b)

Scheme	Marks
Any route e.g. ACFGDCABDEGEBA	B1
Length = 73.3 + their 20.5 = 93.8km	M1 A1
	(3)

Notes

1B1: Any correct route (14 nodes)

1M1: 73.3 + ft their least, from a choice of at least two.

1A1: cao

Mark scheme (c)

Scheme	Marks
The new tunnel would make C and G even. So only BE would need to be repeated.	B1
Extra distance would be 10 + 8.3 = 18.3 < 20.5 [91.6 < 93.8] So it would decrease the total distance.	DB1
	(2)
	(10 marks)

Notes

1B1: A correct explanation, referring to BE and relevant numbers (8.3, 12.2, 2.2, 18.3,81.3, 91.6) maybe confused, incomplete or lack conclusion –bod gets B1

2B1D: A correct, clear explanation all there + conclusion (ft on their numbers.)

D1 January 2010 Q3

EdexcelOld spec10 marksRoute Inspection Shortest Path

Figure 3: network with arcs AB 15, AD 20, AC 19, BE 8, BD 14, CD 12, CF 10, DE 2, DG 6, DF 7, EG 3, EH 15, GH 11, FG 4, FH 21 — Figure 3

[The total weight of the network is 167]

Figure 3 represents a network of paths. The number on each arc gives the time, in minutes, to travel along that path.

(a) Use Dijkstra’s algorithm to find the quickest route from A to H. State your quickest route and the time taken. (5)

Kevin must walk along each path at least once and return to his starting point.

(b) Use an appropriate algorithm to find the time of Kevin’s quickest possible route, starting and finishing at A. You should make your method and working clear. (5)

Mark scheme (b)

Scheme	Marks
Odd nodes are A, B, C, H	M1
AB + CH = 15 + 25 = 40	A1
AC + BH = 19 + 22 = 41	A1
AH + BC = 36 + 22 = 58	A1
(40 is the shortest, repeating AB and CF + FG + GH)
Must be choosing from at least two pairings for this last mark Shortest time = 167 + 40 = 207 minutes. 167 + their shortest	A1ft
	(5)
	(10 marks)

D1 June 2009 Q5

EdexcelOld spec9 marksRoute Inspection

Figure 3: network of paths with vertices A to H and lengths in m — Figure 3

[The total weight of the network is 625 m]

Figure 3 models a network of paths in a park. The number on each arc represents the length, in m, of that path.

Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route.

(a) Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear. (6)

The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.

The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete.

(b) Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route. (3)

Mark scheme (a)

Scheme	Marks
CD + EG = 45 + 38 = 83	M1 1A1
CE + DG = 39 + 43 = 82 ←	2A1
CG + DE = 65 + 35 = 100	3A1
Repeat CE and DG	4A1ft
Length 625 + 82 = 707 (m)	5A1ft
	(6)

Notes

(a) 1M1: Three pairings of their four odd nodes

1A1: one row correct

2A1: two rows correct

3A1: three rows correct

4A1ft: ft their least, but must be the correct shortest route arcs on network. (condone DG)

5A1ft: 625 + their least = a number. Condone lack of m

Mark scheme (b)

Scheme	Marks
DE (or 35) is the smallest	M1
So finish at C.	A1ft
New route 625 + 35 = 660 (m)	A1ft=1B1
	(3)
	(9 marks)

Notes

(b) 1M1: Identifies their shortest from a choice of at least 2 rows.

1A1ft: ft from their least or indicates C.

2A1ft = 1Bft: correct for their least. (Indept of M mark)

D1 January 2009 Q5

EdexcelOld spec8 marksRoute Inspection

Figure 3: network of railway tracks with vertices A to H and lengths in km — Figure 3

(The total weight of the network in Figure 3 is 543 km.)

Figure 3 models a network of railway tracks that have to be inspected. The number on each arc is the length, in km, of that section of railway track.

Each track must be traversed at least once and the length of the inspection route must be minimised.

The inspection route must start and finish at the same vertex.

(a) Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. (5)

It is now permitted to start and finish the inspection at two distinct vertices.

(b) State which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer. (3)

Mark scheme (a)

Scheme	Marks
Odd vertices C, D, E, G	B1
CD + EG = 17 + 19 = 36 ← CE + DG = 12 + 25 = 37 CG + DE = 28 + 13 = 41	M1 A1 A1
Length = 543 + 36 = 579 (km)	A1ft
	(5)

Notes

(a) 1B1: cao (may be implicit)

1M1: Three pairings of their four odd nodes

1A1: one row correct

2A1: all correct

3A1ft: 543 + their least = a number. Condone lack of km

Mark scheme (b)

Scheme	Marks
CE (12) is the shortest	M1
So repeat CE (12)	A1ft
Start and finish at D and G	A1ft
	(3)
	(8 marks)

Notes

(b) 1M1ft: Identifies their shortest from a choice of at least 2 rows.

1A1ft: indicates their intent to repeat shortest.

2A1ft: correct for their least.

D1 June 2008 Q3

EdexcelOld spec9 marksRoute Inspection Shortest Path

Figure 3: network of roads with vertices A to I and lengths in km — Figure 3

Figure 3 shows a network of roads. The number on each arc represents the length, in km, of that road.

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

Sam has been asked to inspect the network and assess the condition of the roads. He must travel along each road at least once, starting and finishing at A.

(b) Use an appropriate algorithm to determine the length of the shortest route Sam can travel. State a shortest route. (4)

(The total weight of the network is 197km)

Dijkstra boxes: A 1 0; D 4 8; C 2 6; B 3 7; E 5 18 (20 18); G 6 19; F 7 24 (25 24); H 8 36 (38 37 36); I 9 48 (49 48) — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
Odd vertices are A and H	B1
Attempt to find shortest route from A to H = ADGH	M1
New length: 197 + 36 = 233	A1ft
Route: e.g. ADGHGDACEDHIFHEFBA (18)	A1
	(4)
	(9 marks)

Notes

(b) 1B1: A and H identified in some way – allow recovery from M mark.

1M1: Accept, if correct, path, or its length. Accept attempt if finding shortest.

1A1ft: 197 + their shortest A to H (36)

2A1: A correct route.

D1 January 2008 Q3

EdexcelOld spec9 marksRoute Inspection

Figure 4: network of roads with vertices A to G and lengths in km — Figure 4

Figure 4 models a network of roads in a housing estate. The number on each arc represents the length, in km, of the road.

The total weight of the network is 11 km.

A council worker needs to travel along each road once to inspect the road surface. He will start and finish at A and wishes to minimise the length of his route.

(a) Use an appropriate algorithm to find a route for the council worker. You should make your method and working clear. State your route and its length. (6)

A postal worker needs to walk along each road twice, once on each side of the road. She must start and finish at A. The length of her route is to be minimised. You should ignore the width of the road.

(b)

(i) Explain how this differs from the standard route inspection problem. (1)

(ii) Find the length of the shortest route for the postal worker. (2)

Mark scheme (a)

Scheme	Marks
CD + FG = 0.7 + 0.6 = 1.3 *	M1 A1
CF + DG = 0.5 + 0.9 = 1.4	A1
CG + DF = 1.1 + 0.5 = 1.6	A1
repeat CD and FG
A possible route e.g. A C D C F G F D G E D A E B A	A1
length: 11 + 1.3 = 12.3 km	A1ft
	(6)

Notes

Q3(a) 1M1 3 distinct pairings of their 4 odd nodes

1A1 one line correct (condone missing total)

2A1 2 lines correct including totals

3A1 All three lines correct including totals

4A1 15 letters, repeat CD and FG, start/finish A, A to G there.

5A1ft 11+ thier minimum

D1 June 2007 Q4

EdexcelOld spec7 marksRoute Inspection

Figure 4: network of tunnels with vertices A to I and arc lengths in km — Figure 4

Figure 4 models a network of underground tunnels that have to be inspected. The number on each arc represents the length, in km, of each tunnel.

Joe must travel along each tunnel at least once and the length of his inspection route must be minimised.

The total weight of the network is 125 km.

The inspection route must start and finish at A.

(a) Use an appropriate algorithm to find the length of the shortest inspection route. You should make your method and working clear. (5)

Given that it is now permitted to start and finish the inspection at two distinct vertices,

(b) state which two vertices should be chosen to minimise the length of the new route. Give a reason for your answer. (2)

D1 January 2007 Q5

EdexcelOld spec7 marksGraphs & Networks Route Inspection

(a) Explain why a network cannot have an odd number of vertices of odd degree. (2)

Figure 4: network of paths on A to I — Figure 4

Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.

(b) Use the route inspection algorithm to find which paths, if any, need to be traversed twice. (4)

Mark scheme (a)

Scheme	Marks
e.g. Each edge contributes 2 to the sum of degrees, hence this sum must be even. Therefore there must be an even (or zero) number of vertices of odd degree Hence there cannot be an odd number of vertices of odd degree	B2,1,0
	(2)

D1 June 2006 Q3

EdexcelOld spec7 marksRoute Inspection

Figure 2: network of pipes on A to I — Figure 2

Figure 2 shows the network of pipes represented by arcs. The length of each pipe, in kilometres, is shown by the number on each arc. The network is to be inspected for leakages, using the shortest route and starting and finishing at \(A\).

(a) Use the route inspection algorithm to fins which arcs, if any, need to be traversed twice. (4)

(b) State the length of the minimum route. [The total weight of the network is 394 km.] (1)

It is now permitted to start and finish the inspection at two distinct vertices.

Mark scheme (a)

Scheme	Marks
\(AC + EG = 44 + 35 = 79\)	M1
\(AE + CG = 41 + 36 = 77\ *\)	A1
\(AG + CE = 36 + 45 = 81\)	A1
Repeat \(AD, DE, CF\) and \(FG\)	A1ft
	(4)

Notes

M1 3 pairs of their odd vertices (different)

A1 One pairing and total correct – i.e. one line correct

A1 all 3 pairings and total correct

A1ft Correct arcs identified – must be 2+ pairings to choose from

Mark scheme (c)

Scheme	Marks
Since \(EG\) is the smallest choose to repeat this hence start and finish at \(A\) and \(C\).	M1 A1ft
	(2)
	(7 marks)

Notes

M1 Identifies \(EG\) (35) as smallest – or identifies their smallest from 2+ pairings & totals

A1ft from 2+ pairings + totals

D1 January 2006 Q2

EdexcelOld spec15 marksMinimum Spanning Trees Route Inspection

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	–	48	117	92	–	–	–
\(B\)	48	–	–	–	–	63	55
\(C\)	117	–	–	28	–	–	85
\(D\)	92	–	28	–	58	132	–
\(E\)	–	–	–	58	–	124	–
\(F\)	–	63	–	132	124	–	–
\(G\)	–	55	85	–	–	–	–

The table shows the lengths, in metres, of the paths between seven vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) in a network N.

(a) Use Prim’s algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. You must clearly state the order in which you selected the edges of your tree, and the weight of your final tree. Draw your tree using the vertices given in Diagram 1 in the answer book. (5)

(b) Draw N using the vertices given in Diagram 2 in the answer book. (3)

(c) Solve the Route Inspection problem for N. You must make your method of working clear. State a shortest route and find its length.
(The weight of N is 802.) (7)

Mark scheme (c)

Scheme	Marks
\(AB + CF = 48 + 160 = 208\)	M1 A1
\(AC + BF = 117 + 63 = 180\ *\)	A1
\(AF + BC = 111 + 140 = 251\)	A1 (4)
e.g. \(ABFBGCACDEFDA\)	A1
length \(802 + 180 = 982\) m	M1 A1ft (3)
	(7)
	(15 marks)

Notes

In the scheme the repeated arcs \(BF\) and \(AC\) are marked in the route.

D1 June 2005 Q3

EdexcelOld spec7 marksRoute Inspection

Figure 2: road network on A to G — Figure 2

Figure 2 models a network of roads which need to be inspected to assess if they need to be resurfaced. The number on each arc represents the length, in km, of that road.

Each road must be traversed at least once and the length of the inspection route must be minimised.

(a) Starting and finishing at \(A\), solve this route inspection problem. You should make your method and working clear. State the length of the shortest route.
(The weight of the network is 77 km.) (5)

Given that it is now permitted to start and finish the inspection at two distinct vertices,

(b) state which two vertices you should choose to minimise the length of the route. Give a reason for your answer. (2)

D1 January 2005 Q5

EdexcelOld spec11 marksRoute Inspection Shortest Path

Figure 3: network of paths on A to H — Figure 3

Figure 3 shows a network of paths. The number on each arc gives the distance, in metres, of that path.

(i) Use Dijkstra’s algorithm to find the shortest distance from \(A\) to \(H\). (5)

(ii) Solve the route inspection problem for the network shown in Figure 3. You should make your method and working clear. State a shortest route, starting at \(A\), and find its length.

[The total weight of the network is 1241]

(6)

Mark scheme (ii)

Scheme	Marks
odd vertices \(B, C, D, G\)	M1
\(BC + DG = 95 + 145 = 240\ *\)	A1
\(BD + CG = 169 + 179 = 348\)	A1
\(BG + CD = 249 + 74 = 323\)	A1
	(4)
Repeat \(BC, DE\) and \(EG\)
e.g. \(ABCBFHGFEGECDEDA\)	B1
length \(1241 + 240 = 1481\) m	B1
	(2)
	(11 marks)