Shortest Path

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)

A2 June 2025 Q3

EdexcelCurrent spec10 marksShortest Path Travelling Salesman

Figure 1: network on villages A to G with arcs AG 11, GF 12, GE 24 (one-way from G to E), GC 47, AE 35, AB 9 (one-way from A to B), AD 25 (one-way from A to D), BF 35, BD 8, BC 40, CD 17, FE 14, FD 31, ED 11 — Figure 1

Direct roads between seven villages, A, B, C, D, E, F and G, are represented in Figure 1. The weight on each arc is the time, in minutes, taken to travel along the corresponding road. Three roads, AB, AD and GE, are one-way, as indicated by the arrow on the corresponding arc.

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

(a) Set up an initial time matrix for this network. (2)

The time matrix after three iterations of Floyd’s algorithm is shown below.

	A	B	C	D	E	F	G
A	–	9	49	17	35	44	11
B	∞	–	40	8	∞	35	87
C	∞	40	–	17	∞	75	47
D	∞	8	17	–	11	31	64
E	35	44	84	11	–	14	46
F	∞	35	75	31	14	–	12
G	11	20	47	28	24	12	–

(b) Perform the next two iterations of Floyd’s algorithm that follow from the table above.
You should show only the time matrix after each iteration. (5)

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

	A	B	C	D	E	F	G
A	–	9	34	17	28	23	11
B	54	–	25	8	19	33	45
C	58	25	–	17	28	42	47
D	46	8	17	–	11	25	37
E	35	19	28	11	–	14	26
F	23	32	42	25	14	–	12
G	11	20	45	28	24	12	–

Albert must visit each village. He will start and finish at B and wishes to minimise the total time taken to visit each village.

(c)

(i) Use the nearest neighbour algorithm, starting at B, to find a Hamiltonian cycle in the complete network of shortest times shown above.

(ii) Find the total travel time for this cycle.

(iii) Given that he travels the Hamiltonian cycle found in (c)(i), interpret this cycle in terms of the actual villages visited by Albert. (3)

Mark scheme (a)

Scheme

Marks

	A	B	C	D	E	F	G
A	-	9	∞	25	35	∞	11
B	∞	-	40	8	∞	35	∞
C	∞	40	-	17	∞	∞	47
D	∞	8	17	-	11	31	∞
E	35	∞	∞	11	-	14	∞
F	∞	35	∞	31	14	-	12
G	11	∞	47	∞	24	12	-

B2, 1, 0

1.1b
1.1b

(2)

Notes

a1B1: At least three rows and three columns correct (condone at most 2 empty cells but accept consistent blanks for the leading diagonal)

a2B1: CAO

Mark scheme (c)

Scheme	Marks	AO
(i) NNA starting at B: B – D – E – F – G – A – C – B	B1	2.2a
(ii) Time taken: 8 + 11 + 14 + 12 + 11 + 34 + 25 = 115 (minutes)	B1	1.1b
(iii) Actual villages visited: BDEFGA\(\underline{\text{BD}}\)C\(\underline{\text{D}}\)B	B1	2.2a
	(3)
	(10 marks)

Notes

ci1B1: CAO (Nearest neighbour cycle starting at B – must include return to B) (condone the use of arcs BD DE EF FG GA AC CB – must be written in this manner and not AG or BC)

cii2B1: Correct time

ciii3B1: Correct route – must be stated as nodes

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 Q3

EdexcelCurrent spec8 marksAlgorithms Shortest Path

Figure 4: network on A to J with edges AB 23, AC 35, AD 41, BC 8, BE 42, BG 37, CD 7, CE 30, CG 28, CH 45, CF 43, DF 34, DH 32, EG 21, EH 7, EJ 50, FG 11, FH 22, GH 10, HJ 32 — Figure 4

Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J.

The number on each edge gives the length of the corresponding edge.

(a)

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

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

One application of Dijkstra’s algorithm has order \(n^2\), where \(n\) is the number of nodes in the network.

It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.

(b) Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes. (2)

Dijkstra labelling from A: A 1 0; B 2 23 (23); C 3 31 (35 31); D 4 38 (41 38); G 5 59 (60 59); E 6 61 (65 61 (80)); H 7 68 (76 70 69 68); F 8 70 (74 72 70 (90)); J 9 100 (111 100) — Mark scheme (a)

Scheme	Marks	AO
(i)	M1 A1 (ABCD) A1 (GEH) A1ft (FJ)	1.1b 1.1b 1.1b 1.1b
Shortest path from A to J is ABCEHJ	A1	2.2a
Length of shortest path is 100	A1ft	2.2a
	(6)

Mark scheme (b)

Scheme	Marks	AO
\(0.0312 \times \left(\dfrac{9000}{9}\right)^2\)	M1	1.1a
= 31 200 seconds therefore 520 minutes	A1	2.2a
	(2)
	(8 marks)

Notes

M1: Complete, correct method – allow reciprocal e.g. \(0.0312 \times \left(\dfrac{9}{9000}\right)^2\) – allow slips in values only e.g. 0.312 for 0.0312. If using anything other than squared e.g. \(n^3\) then M0. The correct answer in seconds, minutes or hours (8 hours 40 minutes) implies this mark (and if in minutes implies the A mark too)

A1: CAO – the exact value of 520 must be stated at some point (as question specifically asked for the answer in minutes) – condone lack of units (but if present must be correct)

AS June 2023 Q3

EdexcelAS paperCurrent spec11 marksMinimum Spanning Trees Shortest Path

Figure 2: weighted network on vertices A to J with edges AB 40, AD 49, AE 45, BC 32, BD 6, BE 28, BF 58, CD 24, CG 41, CH 34, DG 15, EG 11, EF 30, FG 43, FJ 6, GH 23, GJ 50, HJ 61 — Figure 2

Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track.
Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel.

Given that Dijkstra’s algorithm is to be applied only once to find Dyfan’s route,

(a) explain why the algorithm should begin at C. (1)

(b) Use Dijkstra’s algorithm to find the shortest route from A to J via C. State this route and its length. (6)

(c) Use Prim’s algorithm, starting at C, to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree. (3)

(d) State the total length, in km, of the minimum spanning tree. (1)

Mark scheme (a)

Scheme	Marks	AO
Dijkstra’s algorithm only finds the shortest path from a given starting node to all other nodes in the network. If the shortest route from A to J via C is required, then this is equivalent to finding the shortest paths from C to A and C to J and so therefore as C is common to both paths then the algorithm should start at C	B1	3.5b
	(1)

Notes

B1: Recognition that the limitation of the algorithm is that it can only find the shortest path from a given starting node to all others (and not from any node to any other node) and therefore a clear indication is required that C is the starting vertex to of the two required paths that include A and J. As a minimum accept that finding A to J via C is equivalent of finding the shortest (oe) path from C to J and C to A (these two paths must be stated this way round)

Dijkstra labelling from C: C 1 0; D 2 24; B 3 30 (32 30); H 4 34; G 5 39 (41 39 (57)); E 6 50 (58 50); A 7 70 (73 70 (95)); F 8 80 (88 82 80); J 9 86 (95 89 86) — Mark scheme (b)

Dijkstra labelling from A: A 1 0; B 2 40; E 3 45 (45 (68)); D 4 46 (49 46); G 5 56 (56 (61)); C 6 70 (72 70 (97)); F 7 75 (98 75 (99)); H 8 79 (79 (104)); J 9 81 (106 81 (140)) — Mark scheme (b)

Scheme	Marks	AO
	M1 A1 (CDBH) A1 (GEA) A1ft (FJ)	1.1b 1.1b 1.1b 1.1b
Shortest route from A to J via C is A B D C D G E F J	A1	2.2a
Shortest length: 70 + 86 = 156 (km)	A1ft	2.2a
	(6)

Mark scheme (c)

Scheme	Marks	AO
Prim’s algorithm from C: CD, BD, DG; EG, GH, EF; FJ, AB	M1 A1 A1	1.1b 1.1b 1.1b
	(3)

Notes

M1: Prim (not Kruskal) – First three arcs (CD, BD, DG) correctly chosen, or first four nodes (C, D, B, G) correctly chosen in order. If any explicit rejections seen at any point then M1 (max) only. A list of weights alone scores M0.

A1: First six arcs correctly chosen in order (CD, BD, DG, EG, GH, EF), or all nodes correctly chosen in order (C, D, B, G, E, H, F, J, A)

A1: cso (correct solution only) – all arcs correctly stated (not just nodes) and chosen in the correct order (with no additional, incorrect or repeated arcs)

Misread in (c): Starting at a node other than C scores M1 only – must have the first three arcs (or four nodes) correct (and in the correct order). Therefore applying Prim, starting at A, would give AB, BD, DG,… for M1 only

Scheme	Marks	AO
155 (km)	B1	1.1b
	(1)
	(11 marks)

A2 June 2023 Q1

EdexcelCurrent spec7 marksGraphs & Networks Shortest Path

Figure 1: graph G on vertices A, B, C, D and E with edges EA, AB, AC, EB, ED, DB, DC and CB — Figure 1

Figure 1 shows the graph G.

(a) State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer. (1)

(b) Write down an example of a Hamiltonian cycle on G. (1)

(d) State the number of arcs that would need to be added to G to make the graph \(K_5\) (1)

Figure 2: the same graph with weights EA 5, AB 10, EB 4, ED 7, DB 8, AC 15, DC 2, CB 3 — Figure 2

Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. 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 five villages.

(e) For the network represented in Figure 2, complete the initial time matrix in the answer book. (1)

Initial time matrix (answer book)

	A	B	C	D	E
A	–
B		–
C			–
D				–
E					–

The time matrix after four iterations of Floyd’s algorithm is shown in Table 1.

	A	B	C	D	E
A	–	10	13	15	5
B	10	–	3	5	4
C	13	3	–	2	7
D	15	5	2	–	7
E	5	4	7	7	–

Table 1

(f) Perform the final iteration of Floyd’s algorithm that follows from Table 1, showing the time matrix for this iteration. (2)

Mark scheme (a)

Scheme	Marks	AO
Graph G is neither as there are more than two vertices of odd degree	B1	2.4
	(1)

Notes

B1: ‘Neither’ together with a correct reason (ignore irrelevant statements but do not isw incorrect statements)

Examples of B1:

G contains more than 2 odd nodes
G contains 4 odd nodes (or stating that A, C, D and E are odd)
G contains (only) 1 even node
The number of odd degree nodes in G is not 0 or 2

Examples of B0

G contains odd nodes
G contains at least 2 odd nodes
G contains 4 nodes of degree 3 (not linking this to ‘odd’)

Mark scheme (b)

Scheme	Marks	AO
e.g. A – B – C – D – E – A	B1	1.1b
	(1)

Notes

B1: CAO - must begin and end at the same node and include every other node in the graph exactly once. Accept if given in terms of arcs e.g. AC, CB, BD, DE, EA

G redrawn with arc AC moved outside so that no arcs cross — Mark scheme (c)

Scheme	Marks	AO
G is planar as it can be drawn with no arcs intersecting/crossing each other e.g.	B1	2.4
	(1)

Scheme	Marks	AO
2	B1	1.1b
	(1)

Mark scheme (e)

Scheme

Marks

	A	B	C	D	E
A	-	10	15	∞	5
B	10	-	3	8	4
C	15	3	-	2	∞
D	∞	8	2	-	7
E	5	4	∞	7	-

1.1b

(1)

Notes

B1: CAO - no blanks entries (apart from the lead diagonal) and must include \(\infty\) in cells AD, CE, DA, EC)

Mark scheme (f)

Scheme

Marks

	A	B	C	D	E
A	-	[9]	[12]	[12]	5
B	[9]	-	3	5	4
C	[12]	3	-	2	7
D	[12]	5	2	-	7
E	5	4	7	7	-

M1
A1

1.1b
1.1b

(2)

(7 marks)

Notes

M1: No change in the fifth row and fifth column with at least two values reduced correctly (no blank entries – apart from the lead diagonal)

A1: CAO for the final iteration

A2 June 2022 Q3

EdexcelCurrent spec10 marksShortest Path Travelling Salesman

3. The initial distance matrix (Table 1) shows the lengths, in metres, of the corridors connecting six classrooms, A, B, C, D, E and F, in a school. For safety reasons, some of the corridors are one-way only.

	A	B	C	D	E	F
A	–	12	32	24	29	11
B	12	–	17	8	∞	∞
C	32	17	–	4	12	∞
D	24	∞	4	–	∞	13
E	∞	∞	12	18	–	12
F	11	∞	∞	13	12	–

Table 1

(a) By adding the arcs from vertex A, along with their weights, complete the drawing of this network on Diagram 1 in the answer book. (2)

Diagram 1: vertices A to F with arcs BC 17, BD 8 (one-way from B to D), CD 4, CE 12, ED 18 (one-way from E to D), EF 12, DF 13; vertex A has no arcs — Diagram 1

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

The distance matrix after two iterations of Floyd’s algorithm is shown in Table 2.

	A	B	C	D	E	F
A	–	12	29	20	29	11
B	12	–	17	8	41	23
C	29	17	–	4	12	40
D	24	36	4	–	53	13
E	∞	∞	12	18	–	12
F	11	23	40	13	12	–

Table 2

(b) Perform the next two iterations of Floyd’s algorithm that follow from Table 2. You should show the distance matrix after each iteration. (4)

The final distance matrix after completion of Floyd’s algorithm is shown in Table 3.

	A	B	C	D	E	F
A	–	12	24	20	23	11
B	12	–	12	8	24	21
C	28	17	–	4	12	17
D	24	21	4	–	16	13
E	23	29	12	16	–	12
F	11	23	17	13	12	–

Table 3

Yinka must visit each classroom. He will start and finish at E and wishes to minimise the total distance travelled.

(c)

(i) Use the nearest neighbour algorithm, starting at E, to find two Hamiltonian cycles in the completed network of shortest distances.

(ii) Find the length of each of the two cycles.

(iii) State, with a reason, which of the two cycles provides the better upper bound for the length of Yinka’s route. (4)

Scheme	Marks	AO
	M1 A1	1.1b 1.1b
	(2)

Mark scheme (c)

Scheme

Marks

Nearest neighbour routes:

E – C – D – F – A – B – E	Length = 76
E – F – A – B – D – C – E	Length = 59

The cycle that begins E – F –… is the better upper bound as the value is the smaller of the two

M1
A1
A1
A1

3.4
1.1b
1.1b
2.4

(4)

(10 marks)

Notes

(c) M1: Either cycle correct (must include returning to E) – nodes must be in the correct order and therefore not reversed but allow if stated in terms of arcs. If only one cycle correct then M1 only

A1: Both cycles correct – nodes must be in the correct order but allow if stated in terms of arcs

A1: Both cycles and corresponding lengths correct

A1: Correct reasoning that the smallest (oe) value is the better upper bound – dependent on all previous marks in this part (cso)

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)

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)

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 Q6

EdexcelCurrent spec10 marksAlgorithms Shortest Path

Figure 4: network on A to H with arcs AB 32, AC 16, AD 75, AF 95, BD 33, BE 15, CD 50, CF 70, CG 105, CH 113, DE 17, DG 50, EF 30, FG 25, FH 41, GH 10 — Figure 4

In Figure 4 the weights on the arcs represent distances.

(a)

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

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

One application of Dijkstra’s algorithm has order \(n^2\), where \(n\) is the number of nodes in the network. A computer produces a table of shortest distances between any two different nodes by repeatedly applying Dijkstra’s algorithm from each node of the network.

It takes the computer 0.082 seconds to produce a table of shortest distances for a network of 10 nodes.

(b) Calculate approximately how long it will take, in seconds, for the computer to produce a table of shortest distances for a network with 200 nodes. You must give a reason for your answer. (3)

Dijkstra boxes (vertex, order of labelling, final value; working values): A 1, 0; C 2, 16 (16); B 3, 32 (32); E 4, 47 (47); D 5, 64 (75 66 65 64); F 6, 77 (95 86 77); G 7, 102 (121 114 102); H 8, 112 (129 118 112) — Mark scheme (a)

Mark scheme (b)

Scheme	Marks	AO
Applying Dijkstra repeatedly to \(n\) nodes implies that the order is \(n(n^2) = n^3\)	B1	3.1b
\(t = 0.082\left(\dfrac{200}{10}\right)^3\)	M1	3.4
= 656 (seconds)	A1	2.2a
	(3)

Notes

(b) B1: Any indication that repeated application of Dijkstra has cubic order

M1: Complete method – allow 10/200 – allow slips in values e.g. 0.82 for 0.082 and accept 200/10 (or 10/200) either squared or cubed only

A1: cao

Mark scheme (c)

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

Notes

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

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.

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)

A2 October 2020 Q3

EdexcelCurrent spec9 marksShortest Path Travelling Salesman

Figure 2: network on A, B, C, D and E with arcs AB 8, AC 4, AD 7, BC 3, BE 10, CE 6, DE 1 and DC 1 (one-way from D to C) — Figure 2

Direct roads between five villages, A, B, C, D and E, are shown in Figure 2. The weight on each arc is the time, in minutes, it takes to travel along the corresponding road. The road from D to C is one-way as indicated by the arrow on the corresponding arc.

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

(a) Set up initial time and route matrices. (2)

The matrices after two iterations of Floyd’s algorithm are shown below.

Time matrix

	A	B	C	D	E
A	–	8	4	7	18
B	8	–	3	15	10
C	4	3	–	11	6
D	7	15	1	–	1
E	18	10	6	1	–

Route matrix

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

(b) Perform the next two iterations of Floyd’s algorithm that follow from the tables above. You should show the time and route matrices after each iteration. (4)

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

Final time matrix

	A	B	C	D	E
A	–	7	4	7	8
B	7	–	3	10	9
C	4	3	–	7	6
D	5	4	1	–	1
E	6	5	2	1	–

(c)

(i) Use the nearest neighbour algorithm, starting at A, to find a Hamiltonian cycle in the complete network of shortest times.

(ii) Find the time taken for this cycle.

(iii) Interpret the cycle in terms of the actual villages visited. (3)

Mark scheme (c)

Scheme	Marks	AO
(i) NNA: A – C – B – E – D – A	B1	1.1b
(ii) 4 + 3 + 9 + 1 + 5 = 22 minutes	dB1	1.1b
(iii) A – C – B – C – E – D – C – A	B1	3.2a
	(3)
	(9 marks)

Notes

(c)(i) B1: CAO

(c)(ii) dB1: CAO – not from A – C – D – E – B – A

(c)(iii) B1: CAO

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)

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 Q3

EdexcelCurrent spec14 marksShortest Path Travelling Salesman

Figure 2: network on A, B, C, D and E with arcs AB 15, AC 7, AD 18, AE 3 (one-way from A to E), CB 5 (one-way from C to B), CD 4, CE 9, DE 3 — Figure 2

The network in Figure 2 shows the direct roads linking five villages, A, B, C, D and E. The number on each arc represents the length, in miles, of the corresponding road. The roads from A to E and from C to B are one-way, as indicated by the arrows.

(a) Complete the initial distance and route tables for the network provided in the answer book. (2)

Initial distance table (answer book)

	A	B	C	D	E
A
B
C
D
E

Initial route table (answer book)

	A	B	C	D	E
A
B
C
D
E

(b) Perform the first three iterations of Floyd’s algorithm. You should show the distance table and the route table after each of the three iterations. (5)

After five iterations of Floyd’s algorithm the final distance table and partially completed final route table are shown below.

Distance table

	A	B	C	D	E
A	–	12	7	6	3
B	15	–	22	21	18
C	7	5	–	4	7
D	11	9	4	–	3
E	14	12	7	3	–

Route table

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

(c)

(i) Explain how the partially completed final route table can be used to find the shortest route from E to A.

(ii) State this route. (3)

Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table.

(d)

(i) State the cycle obtained using the nearest neighbour algorithm.

(ii) State the length of this cycle.

(iii) Interpret the cycle in terms of the actual villages visited.

(iv) Prove that Mabintou’s cycle is not optimal. (4)

Mark scheme (c)

Scheme	Marks	AO
(i) Start at E(5^th row) and read across to the A (1^st column), there is a D there so the route from E to A is via D	B1	2.4
Now consider both E to D and D to A – for E reading across to the D (4^th column), there is a D indicating that the shortest path from E to D is ED. For D reading across to the A (1^st column), there is a C indicating that the shortest path from D to A is via C	dB1	2.4
(ii) EDCA	B1	2.2a
	(3)

Notes

(c) B1: Row E column A is D so the route is E to A via D (or implies that the order of the nodes in the route is EDA) or D implied from general argument or Row E column A is D therefore the route begins ED (in all cases must clearly imply row E and column A)

dB1: Row D column A is C therefore the route goes via C (before A) or complete general argument that allows the route from D to A to be found or allow those who say that row D column A is C so the route is EDC and then row C column A is A

B1: CAO (EDCA)

Mark scheme (d)

Scheme	Marks	AO
(i) NNA: D – E – C – B – A – D	B1	1.1b
(ii) 3 + 7 + 5 + 15 + 6 = 36 miles	B1	1.1b
(iii) D – E – D – C – B – A – E – D	B1	3.2a
(iv) e.g. the cycle A – E – D – C – B – A has a length of 30 miles \(\lt\) 36 miles so Mabintou’s route is not optimal	B1	2.4
	(4)
	(14 marks)

Notes

(d)(i) B1: CAO (D – E – C – B – A – D)

(ii) B1: CAO (36 – no units required)

(iii) B1: CAO (D – E – D – C – B – A – E – D) or mentions that the cycle would visit E twice and D three times (or visit D before the end of the cycle – if D visited once stated and it is not clear that this isn’t the start or finish then B0) or mention of E to C via D and A to D via E

(iv) B1: A correct cycle stated (e.g. a cyclic permutation of A – E – D – C – B – A) with corresponding correct length – dependent on second B mark in this part (so must have had 36 in (d)(ii))

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)

AS June 2018 Q1

EdexcelAS paperCurrent spec9 marksAlgorithms Shortest Path

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

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

(a)

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

(ii) State the quickest route. (6)

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

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

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

Mark scheme (b)

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

Notes

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

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

Mark scheme (c)

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

Notes

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

D1 June 2019 Q3

EdexcelOld spec11 marksMinimum Spanning Trees Shortest Path

	A	B	C	D	E	F	G	H	J
A	–	3	8	5	–	–	–	–	–
B	3	–	4	–	–	–	–	–	–
C	8	4	–	–	9	4	–	–	–
D	5	–	–	–	–	7	4	9	–
E	–	–	9	–	–	4	–	–	7
F	–	–	4	7	4	–	–	8	13
G	–	–	–	4	–	–	–	4	–
H	–	–	–	9	–	8	4	–	7
J	–	–	–	–	7	13	–	7	–

The table above shows the lengths, in metres, of the paths between nine vertices, A, B, C, D, E, F, G, H and J.

(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges and state its weight. Draw your minimum spanning tree using the vertices in the answer book. (5)

(b) State whether your minimum spanning tree is unique. Justify your answer. (1)

Minimum spanning tree: AB, BC, CF, EF, AD, DG, GH, with EJ or HJ dashed — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
No – there are two different MST (with a weight of 35) either with EJ or HJ	B1
	(1)

Notes

b1B1: CAO – no (oe) + mention of two different MST with either arc EJ or HJ – as a minimum must mention EJ and HJ – or clearly implied that the final arc in the MST could be replaced with the other arc (e.g. if final arc in MST is EJ they must then say that HJ could replace the final arc in the MST) (do not award this mark if the candidate believes that unique means that there is more than one MST)

Dijkstra working: A 1 0; B 2 3; D 3 5; C 4 7 (8 7); G 5 9; F 6 11 (12 11); H 7 13 (14 13 (19)); E 8 15 (16 15); J 9 20 (24 20 (22)) — Mark scheme (c)

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 Q4

EdexcelOld spec12 marksMinimum Spanning Trees Shortest Path

Figure 3: weighted network of tram tracks with vertices A to K — Figure 3

Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.

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

On another day, Sarah wishes to travel from A to F via J.

(b) Find a route of minimal length that goes from A to F via J and state its length. (2)

(c) Use Prim’s algorithm, starting at G, to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree. (3)

(d) State the length, in miles, of the minimum spanning tree. (1)

Dijkstra labelling: A 1 0; B 2 5; E 3 18; C 4 22; K 5 25; D 6 37; J 7 40; H 8 42; G 9 46; F 10 48 — Mark scheme (a)

Mark scheme (c)

Scheme	Marks
Prim starting at G: GF, GH, FJ, DG, JK, EK, BE, AB, CD or GF, GH, FJ, DG, CD, JK, EK, BE, AB	M1 A1 A1
	(3)

Notes

c1M1: First four arcs correctly chosen in order (GF, GH, FJ, DG) or first five nodes correctly chosen in order (G, F, H, J, D). If any explicit rejections seen at any point then M1 (max) only. Do not accept only a list of weights for this mark. Candidates may apply Prim in matrix form so the order of the nodes may be seen at the top of a matrix – accept {-, -, -, 5, -, 2, 1, 3, 4, -} for the M mark

c1A1: First seven arcs correctly chosen in order (GF, GH, FJ, DG, JK, EK, BE or GF, GH, FJ, DG, CD, JK, EK) or all ten nodes correctly chosen in order (G, F, H, J, D, K, E, B, A, C or G, F, H, J, D, C, K, E, B, A) Candidates may apply Prim in matrix form so the order of the nodes may be seen at the top of a matrix – accept {9, 8, 10, 5, 7, 2, 1, 3, 4, 6} or {10, 9, 6, 5, 8, 2, 1, 3, 4, 7} – do not condone any missing numbers e.g. the number 10 must be above either the C or the A

c2A1: CSO – all arcs correctly 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 the matrix unless the correct list of arcs (in the correct order) is also seen)

Misread: Starting at a node other than G scores M1 only in (c) – must have the first four arcs (or five nodes) correct (and in the correct order). The most common misread is those that start at A so for M1 only – accept AB, BE, EK, JK or A, B, E, K, J

D1 June 2015 Q3

EdexcelOld spec10 marksShortest Path

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

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

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

(b) Explain how you determined the shortest route from your labelled diagram. (2)

Dijkstra labelling: A 1 0; B 2 5; F 3 7; D 4 9; C 5 10; G 6 14; H 7 15; E 8 16; J 9 22 — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
E.g. 22 – 7 = 15 JH, 15 – 1 = 14 HG, 14 – 5 = 9 GD, 9 – 2 = 7 DF, 7 – 2 = 5 FB, 5 – 5 = 0 BA Or Trace back from J including arc XY if (Y already lies on the path and) the difference of the final values of X and Y equals the weight of arc XY.	B2, 1, 0
	(2)

Notes

For (b) candidates usually give either a general explanation or a demonstration of how they determined their shortest route. If a candidate gives both a general explanation and a demonstration then mark both and award the best mark (but do not mix the two schemes together)

General Explanation:

For the first B mark any indication of ‘working backwards’ or ‘tracing back’ through the network – it must be clear from the candidates explanation that they are considering working backwards through the network but give bod for seeing just the phrase ‘working backwards’ (oe)

For the second B mark we must see

Working backwards from J
Including an arc (XY) if the difference of the final values (of X and Y) is equal to the weight (of the arc XY)

Must include all the words in bold (or their equivalent, for example, distance for weight, edge for node,…) – technical language must be correct

Demonstration:

For the first B mark we must see two consecutive correct calculations working backwards from J for their network. They do not have to link the corresponding nodes for this first mark, for example, 22 – 7 = 15, 15 – 1 = 14 is sufficient for this mark (also note that 22 – 15 = 7, etc. is equivalent). Condone poor notation for this mark, for example, 22 – 7 = 15 – 1 = 14… is fine for B1

For the second B mark we must see all the correct calculations (so no follow through) from J to A and the linking of all arcs/nodes to these calculations, for example, J: 22 – 7 = 15 H, H: 15 – 1 = 14 G, etc. is acceptable. All values (including the 22 and 0) and nodes (including J and A) must be present

Mark scheme (c)

Scheme	Marks
Shortest route: A – B – F – D – G – E – G – H – J	B1
Length: 26 (km)	B1
	(2)
	(10 marks)

Notes

c1B1: CAO shortest route (A – B – F – D – G – E – G – H – J)

c2B1: CAO correct length (26) – condone lack of units

D1 June 2014 (R) Q3

EdexcelOld spec9 marksShortest Path

Figure 3: weighted network of roads with vertices S, A, B, C, D, E, F, G, T — Figure 3

Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to traverse each road.

(a) Use Dijkstra’s algorithm to find the quickest route from S to T. State your quickest route and the time taken. (6)

It is now necessary to include E in the route.

(b) Determine the effect that this will have on the time taken for the journey. You must state your new quickest route and the time it takes. (3)

Dijkstra labelling: S 1 0; A 2 18; C 3 30; F 4 41; B 5 45; D 6 50; E 7 61; G 8 62; T 9 72 — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
Shortest paths S to T including E: SACFDET	DB1
Time is 75 (minutes), so 3 (minutes) longer.	B1, B1ft
	(3)
	(9 marks)

Notes

b1DB1: Must have scored the M mark in (a). Path correct.

b1B1: CAO time of new route correct.

b2B1ft: Time difference correct (ft their previous times).

D1 June 2014 Q5

EdexcelOld spec9 marksShortest Path

Figure 2: network of roads between Preston, Blackburn, Skipton, York, Accrington, Leeds, Chorley, Horwich, Wigan and Manchester with lengths in miles — Figure 2

Sharon is planning a road trip from Preston to York. Figure 2 shows the network of roads that she could take on her trip. The number on each arc is the length of the corresponding road in miles.

(a) Use Dijkstra’s algorithm to find the shortest route from Preston (P) to York (Y). State the shortest route and its length. (6)

Sharon has a friend, John, who lives in Manchester (M). Sharon decides to travel from Preston to York via Manchester so she can visit John. She wishes to minimise the length of her route.

(b) State the new shortest route. Hence calculate the additional distance she must travel to visit John on this trip. You must make clear the numbers you use in your calculation. (3)

Dijkstra labelled diagram: P 1 0; B 2 10; C 3 12; A 4 16; W 5 23; H 6 27; M 7 41; S 8 42; L 9 68; Y 10 89 — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
Shortest route: P – C – H – M – L – Y	B1
Difference in routes: (41 + 40 + 21) – 89 = 13 (miles)	M1 A1
	(3)
	(9 marks)

Notes

b1B1 CAO for the route

b1M1 Their final value at M + 40 + 21 - accept a value of 102 (with no other working) for this mark.

b1A1 CAO (condone lack of units) – accept, as a minimum,102 followed by 13 for both marks. If 13 with no working then award the previous M mark but withhold the final A mark

D1 June 2013 (R) Q7

EdexcelOld spec7 marksShortest Path

Figure 5: network of roads C1, C2, D, E, F, G, H, I, J with lengths in miles — Figure 5

Figure 5 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. A large crane is required at J and it may be transported from either C₁ or C₂. A route of minimum length is required.

It is decided to use Dijkstra’s algorithm to find the shortest routes between C₁ and J and between C₂ and J.

(a) Explain why J, rather than C₁ or C₂, should be chosen as the starting vertex. (1)

(b) Use Dijkstra’s algorithm to find the shortest route needed to transport the crane. State your route and its length. (6)

Dijkstra labelled diagram from J: J 1 0; H 2 15; I 3 16; G 4 28; F 5 34; E 6 39; D 7 41; C2 8 48; C1 9 49 — Mark scheme (b)

D1 June 2013 Q4

EdexcelOld spec8 marksShortest Path

Figure 3: network of roads S, A, B, C, D, E, F, G, H, T with lengths in miles — Figure 3

Figure 3 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Liz wishes to travel from S to T.

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

On a particular day, Liz must include F in her route.

(b) Find the shortest path from S to T that includes F, and state its length. (2)

Dijkstra labelled diagram: S 1 0; C 3 9; A 2 8; B 5 13; D 4 12; F 6 20; G 7 21; E 8 25; H 9 26; T 10 30 — Mark scheme (a)

D1 January 2013 Q4

EdexcelOld spec11 marksGraphs & Networks Shortest Path

Figure 4: network of canals S, A, B, C, D, E, F, T with lengths in miles — Figure 4

(a) Explain what is meant, in a network, by the term path. (2)

Figure 4 represents a network of canals. The number on each arc represents the length, in miles, of the corresponding canal.

(b) Use Dijkstra’s algorithm to find the shortest path from S to T. State your path and its length. (6)

Next week the canal represented by arc AB will be closed for dredging.

(d) Find a shortest path from S to T avoiding AB and state its length. (2)

Mark scheme (a)

Scheme	Marks
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
	(2)

Notes

a1B1 One of the three points made clearly or two suggested. Arcs (edges)/ vertices (nodes) must be referred to correctly. Do not condone incorrect technical language e.g. point for vertex.

a2B1 All three points made clearly.

Dijkstra labelled diagram: S 1 0; B 2 5; C 3 12; A 4 13; D 5 24; F 6 29; E 7 32; T 8 40 — Mark scheme (b)

D1 June 2012 Q5

EdexcelOld spec10 marksShortest Path

Figure 4: network of roads S, A, B, C, D, E, F, T with lengths in miles — Figure 4

Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.

(a) Use Dijkstra’s algorithm to find the shortest route from S to T. State your shortest route and its length. (6)

(b) Explain how you determined your shortest route from your labelled diagram. (2)

Due to flooding, the roads in and out of D are closed.

Dijkstra labelled diagram: S 1 0; C 2 8; F 3 14; A 4 16; B 5 23; D 6 33; E 7 45; T 8 65 — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
E.g. 65 – 20 = 45 ET; 45 – 12 = 33 DE; 33 – 10 = 23 BD; 23 – 9 = 14 FB; 14 – 6 = 8 CF; 8 – 8 = 0 SC Or Work back from T, including arc XY if the weight of arc XY = the difference in the final values of X and Y.	B2ft, 1ft, 0
	(2)

Notes

b1B1ft Attempting an explanation, at least 3 stages or one half of general explanation.

b2B1ft Correct explanation – all stages, both halves of explanation

Amplification for (b)

General explanation:

1B1 for partial explanation e.g. ‘working backwards/traceback’ or ref to arcs and final value differences

2B1 for working backwards from T + include an arc XY if weight of XY = final value of Y – final value of X.

Demonstration:

1B1 for three correct calculations for their network

2B1 for all calculations correct and linking arcs/nodes to those calculations. Arc lengths and final values visible.

D1 January 2012 Q4

EdexcelOld spec9 marksShortest Path

Figure 5: network with edges AC 37, AD 68, AB 20, BD 45, BE 40, CH 20, CF 48, CD 27, DF 20, DE 12, EG 15, FH 20, FI 15, FG 20, GI 18, HJ 71, IJ 22 — Figure 5

Figure 5 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Olivia wishes to travel from A to J as quickly as possible.

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

On a particular day Olivia must include G in her route.

(b) Find a route of minimal time from A to J that includes G, and state its length (2)

Dijkstra labelling: A 1 0; B 2 20 (20); C 3 37 (37); H 4 57 (57); E 5 60 (60); D 6 64 (68 65 64 (72)); G 7 75 (75); F 8 77 (85 77 (84) (95)); I 9 92 (93 92); J 10 114 (128 114) — Mark scheme (a)

D1 June 2011 Q6

EdexcelOld spec10 marksShortest Path

Figure 6: network with arcs AB 25, AC 11, AD 27, BC 10, BG 43, BE 29, CE 40, CD 13, DF 15, EF 10, EG 10, EH 30, FH 53, GH 12 — Figure 6

Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track.

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

(b) Explain how you determined your shortest route from your labelled diagram. (2)

The track between E and F is now closed for resurfacing and cannot be used.

Dijkstra labelling: A 1 0; C 2 11 (11); B 3 21 (25 21); D 4 24 (27 24); F 5 39 (39); E 6 49 (51 50 49); G 7 59 (64 59); H 8 71 (92 79 71) — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
E.g. 71 – 12 = 59 GH 49 – 10 = 39 FE 24 – 13 = 11 CD 59 – 10 = 49 EG 39 – 15 = 24 DF 11 – 11 = 0 AC Or Trace back from H including arc XY if (Y already lies on the path and) the difference of the final values of X and Y equals weight of arc XY.	B2,1,0
	(2)

Notes

(b)1B1 Attempting an explanation, at least 3 stages or one half of general explanation

2B1 Correct explanation – all six stages, both halves of explanation

D1 January 2011 Q1

EdexcelOld spec8 marksShortest Path

Figure 1: network with arcs AE 14, AC 9, AB 4, BC 3, BD 10, CE 3, CF 14, CD 2, DF 10, DH 16, EG 4, EF 8, FG 3, FH 4, GH 8 — Figure 1

Figure 1 shows a network of roads between eight villages, A, B, C, D, E, F, G and H. The number on each arc gives the length, in miles, of the corresponding road.

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

(b) State your shortest route. (1)

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

Mark scheme (c)

Scheme	Marks
Shortest route: H F G E C	B1ft
Length of shortest route: 21 – 7 = 14 miles	B1ft
	(2)
	(8 marks)

Notes

1B1ft: only ft if their shortest route goes through C, in which case accept their route reversed up to C (either way round)

2B1ft: only ft if their shortest route goes through C, in which case accept their route length (or final value at H) -7.

D1 June 2010 Q6

EdexcelOld spec9 marksShortest Path

Figure 5: network with arcs SA 24, SC 61, SB 18, AD 42, AC 34, BC 42, BE 12, CD 7, CF 15, CE 28, DF 23, DG 12, FG 38, FE 11, FH 35, EH 47, GT 14, HT 11 — Figure 5

Figure 5 shows a network of cycle tracks within a national park. The number on each arc represents the time taken, in minutes, to cycle along the corresponding track.

(a) Use Dijkstra’s algorithm to find the quickest route from S to T. State your quickest route and the time it takes. (6)

(b) Explain how you determined your quickest route from your labelled diagram. (2)

Dijkstra labelling: S 1 0; B 2 18 (18); A 3 24 (24); E 4 30 (30); F 5 41 (41); C 6 56 (61 60 58 56); D 7 63 (66 64 63); G 8 75 (79 75); H 9 76 (77 76); T 10 87 (89 87) — Mark scheme (a)

Mark scheme (b)

Scheme	Marks
Accept demonstration of relevant subtractions, or general explanation.	B2ft,1ft, 0
	(2)

Notes

1B1ft: Partially complete account, maybe muddled, bod gets B1

2B1ft: Complete, clear account.

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 Q6

EdexcelOld spec7 marksShortest Path

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

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

(a) Use Dijkstra’s algorithm to find the shortest distance from A to I. State your shortest route. (6)

(b) State the shortest distance from A to G. (1)

Dijkstra boxes: A 1 0; B 2 8; D 3 14; F 4 19 (25 19); E 5 20; C 6 21 (26 22 21); G 7 28 (34 28 (30) (30)); H 8 29 (29 (36)); I 9 36 (46 45 36) — Mark scheme (a)

D1 January 2009 Q6

EdexcelOld spec7 marksShortest Path

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

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

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

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

(b) State this new minimal route and its length. (2)

Dijkstra boxes: A 1 0; B 2 26; C 3 51 (52 51); D 4 74; E 5 89 (98 89); G 6 113 (123 113); F 7 122; H 8 156 (157 156 (174)) — Mark scheme (a)

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 June 2006 Q4

EdexcelOld spec12 marksGraphs & Networks Shortest Path

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

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

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

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

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

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

Mark scheme (a)

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

Notes

B2 A good, complete description

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

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

Mark scheme (c)

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

Notes

B2ft complete version of one of the 2 given explanations

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

D1 June 2005 Q6

EdexcelOld spec10 marksShortest Path

Figure 5: road network on A to J — Figure 5

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

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

(b) Explain how you determined the shortest route from your labelled diagram. (2)

The road from \(C\) to \(F\) will be closed next week for repairs.

Mark scheme (b)

Scheme	Marks
General explanation – trace back from \(J\) – include arc \(XY\) if \(Y\) is already on path and if difference in final labels equals length of arc. Specific explanation – \(53 - 15 = 38\ \ GJ\) \(38 - 6 = 32\ \ EG\) \(32 - 4 = 28\ \ FE\) \(28 - 10 = 18\ \ CF\) \(18 - 18 = 0\ \ AC\)	B2ft,1ft,0
	(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)