Skip to the worksheet
Revision Library
Choose a subject

Decision Maths: Shortest Paths and Route Inspection - Worksheets, Questions and Revision

26 original exam-style questions - 24 pages of questions with a full mark scheme - free printable PDF.

This topic is chapter 3 of A Level Further Maths Decision Topic Workbook and chapter 1 of A Level Further Maths 10-Minute Tests 2.

Revision Library
revisionlibrary.co.uk
A-Level · EDEXCEL

4.3 Decision Maths: Shortest Paths and Route Inspection

EDEXCEL 9FM0 · Calculator allowed · about 230 minutes
Total Marks
Name: _______________________________    Date: ____ / ____ / ______
Answer ALL questions. Show all your working.
1
This question concerns general properties of algorithms used to estimate the length of an optimal tour in a travelling salesman problem.
(a)State one limitation of using the nearest neighbour algorithm, rather than an exhaustive search, to solve a travelling salesman problem.(1)
(b)State one advantage of using the nearest neighbour algorithm, rather than an exhaustive search of every possible route, for a large network.(1)
(c)Explain why deleting a different vertex before finding a minimum spanning tree can give a different value for the lower bound.(1)
(Total for Question 1 is 3 marks)
2
A network has vertices A, B, C, D, E, F and the following weighted arcs, which must all be traversed: AB = 22, AC = 2, AD = 20, AE = 38, BC = 19, BD = 21, CD = 23, CE = 4, CF = 31, DE = 35, DF = 12. The total weight of all the arcs is 227.
Diagram NOT accurately drawn
ABCDEF22220381921234313512
(a)Identify the vertices of odd degree.(2)
(b)Find the shortest distance between each pair of odd vertices, and hence find the combination of repeated arcs of least total weight that makes the network Eulerian.(3)
(c)Find the length of a shortest closed route that traverses every arc at least once.(2)
(Total for Question 2 is 7 marks)
3
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AC = 7, AD = 32, AG = 13, BD = 23, BE = 35, BF = 31, BG = 17, CE = 5, CF = 29, CG = 12, DF = 21, EG = 14.
Diagram NOT accurately drawn
ABCDEFG7321323353117529122114
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to G and its length.(2)
(Total for Question 3 is 5 marks)
4
A network has vertices A, B, C, D, E, F, G and the following weighted arcs, which must all be traversed: AC = 34, AD = 5, AF = 8, BC = 23, BD = 18, BF = 6, CD = 4, CE = 13, CF = 15, DE = 11, FG = 26. The total weight of all the arcs is 163.
Diagram NOT accurately drawn
ABCDEFG345823186413151126
(a)Identify the vertices of odd degree.(2)
(b)Find the shortest distance between each pair of odd vertices, and hence find the combination of repeated arcs of least total weight that makes the network Eulerian.(3)
(c)Find the length of a shortest closed route that traverses every arc at least once.(2)
(Total for Question 4 is 7 marks)
5
A network has vertices A, B, C, D, E, F and the following weighted arcs, which must all be traversed: AD = 24, AE = 12, AF = 19, BD = 11, BE = 37, BF = 33, CF = 26, DE = 18, DF = 16, EF = 38. The total weight of all the arcs is 234.
Diagram NOT accurately drawn
ABCDEF24121911373326181638
(a)Identify the vertices of odd degree.(2)
(b)Find the shortest distance between each pair of odd vertices, and hence find the combination of repeated arcs of least total weight that makes the network Eulerian.(3)
(c)Find the length of a shortest closed route that traverses every arc at least once.(2)
(Total for Question 5 is 7 marks)
6
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 32, AD = 15, AG = 20, BC = 8, BD = 14, BE = 2, BF = 25, BG = 30, CD = 21, CG = 29, EF = 11, EG = 24.
Diagram NOT accurately drawn
ABCDEFG3215208142253021291124
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to G and its length.(2)
(Total for Question 6 is 5 marks)
7
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 21, AC = 2, AE = 23, AF = 19, AG = 32, BG = 14, CD = 16, CE = 4, CF = 39, DE = 15, DG = 26.
Diagram NOT accurately drawn
ABCDEFG21223193214164391526
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to G and its length.(2)
(Total for Question 7 is 5 marks)
8
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 13, AC = 3, AD = 11, AE = 37, BE = 17, CD = 21, CE = 25, CF = 29, DF = 10, DG = 27, EF = 12, EG = 2.
ABCDEFG1331137172125291027122
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to G and its length.(2)
(Total for Question 8 is 5 marks)
9
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 34, AC = 17, AE = 33, AF = 21, BE = 12, BF = 4, CF = 20, DE = 13, DF = 22.
ABCDEF34173321124201322
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to F and its length.(2)
(Total for Question 9 is 5 marks)
10
A network has vertices A, B, C, D, E, F and the following weighted arcs: AD = 20, AE = 14, AF = 3, BD = 16, BE = 35, CD = 22, CE = 18, CF = 5, DE = 28, DF = 15, EF = 37.
ABCDEF20143163522185281537
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to F and its length.(2)
(Total for Question 10 is 5 marks)
11
A network has vertices A, B, C, D, E, F and the following weighted arcs, which must all be traversed: AC = 18, AE = 38, AF = 17, BD = 39, BE = 8, CD = 22, DE = 26, EF = 7. The total weight of all the arcs is 175.
ABCDEF18381739822267
(a)Identify the vertices of odd degree.(2)
(b)Find the shortest distance between each pair of odd vertices, and hence find the combination of repeated arcs of least total weight that makes the network Eulerian.(2)
(c)Find the length of a shortest closed route that traverses every arc at least once.(2)
(Total for Question 11 is 6 marks)
12
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 34, AC = 2, AD = 20, AE = 3, BD = 29, BE = 32, BF = 28, CD = 33, CF = 17.
ABCDEF3422032932283317
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to F and its length.(2)
(Total for Question 12 is 5 marks)
13
A network has vertices A, B, C, D, E, F and the following weighted arcs, which must all be traversed: AB = 39, AC = 11, AD = 36, BD = 17, BF = 2, CF = 29, DE = 27, DF = 8, EF = 6. The total weight of all the arcs is 175.
ABCDEF391136172292786
(a)Identify the vertices of odd degree.(2)
(b)Find the shortest distance between each pair of odd vertices, and hence find the combination of repeated arcs of least total weight that makes the network Eulerian.(2)
(c)Find the length of a shortest closed route that traverses every arc at least once.(2)
(Total for Question 13 is 6 marks)
14
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 25, AC = 15, AD = 13, BC = 21, BD = 32, BE = 27, BF = 30, DF = 20.
ABCDEF2515132132273020
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to F and its length.(2)
(Total for Question 14 is 5 marks)
15
A small network has vertices A, B, C, D. The only arcs are AB = 1, AC = 2, BD = 100, CD = 2 (there is no direct arc between B and C, or between A and D).
Diagram NOT accurately drawn
ABCD121002
(a)State the length of the path A-B-D.(1)
(b)Find the length of the shortest path from A to D, showing your working.(2)
(c)A student suggests that, to find a shortest path, you can simply move at each vertex along whichever available arc has the smallest weight (a 'greedy' rule). Using this network, starting at A, explain why this rule does not guarantee that the shortest path is found.(2)
(Total for Question 15 is 5 marks)
16
A network has vertices A, B, C, D, E, F, G and the following weighted arcs, which must all be traversed: AC = 5, AD = 21, AE = 38, AG = 15, BD = 20, BG = 11, CE = 13, CG = 24, DF = 14, DG = 4. The total weight of all the arcs is 165.
ABCDEFG521381520111324144
(a)Identify the vertices of odd degree.(2)
(b)Find the shortest distance between each pair of odd vertices, and hence find the combination of repeated arcs of least total weight that makes the network Eulerian.(2)
(c)Find the length of a shortest closed route that traverses every arc at least once.(2)
(Total for Question 16 is 6 marks)
17
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 36, AF = 20, AG = 11, BG = 39, CG = 18, DE = 37, DF = 5, DG = 8, EF = 32, FG = 10.
ABCDEFG362011391837583210
(a)Use Dijkstra's algorithm to find the shortest distance from A to every vertex, listing the vertices in the order in which they become permanently labelled, with their final labels.(3)
(b)State the shortest route from A to G and its length.(2)
(Total for Question 17 is 5 marks)
18
A network has vertices A, B, C, D, E, F, G and the following weighted arcs, which must all be traversed: AB = 34, AE = 38, AG = 31, BD = 14, BF = 3, BG = 39, CF = 32, CG = 36, DE = 20, EG = 19. The total weight of all the arcs is 266.
ABCDEFG3438311433932362019
(a)Identify the vertices of odd degree.(2)
(b)Find the shortest distance between each pair of odd vertices, and hence find the combination of repeated arcs of least total weight that makes the network Eulerian.(2)
(c)Find the length of a shortest closed route that traverses every arc at least once.(2)
(Total for Question 18 is 6 marks)
19
A telecoms engineer, Priya, must inspect every cable route in the network below at least once. The network has vertices P, Q, R, S, T and arcs (lengths in km): PQ = 3, PR = 4, QR = 2, QS = 5, RS = 6, RT = 7, ST = 1.
Diagram NOT accurately drawn
PQRST3425671
(a)Explain why Priya can inspect every cable route exactly once, without repeating any route, if she starts at Q and finishes at S (or starts at S and finishes at Q), and hence state the total length of this inspection route.(3)
(b)Priya is instead required to start and finish her inspection at P. Find the extra distance that she must walk, and hence the length of the shortest closed route, starting and finishing at P, that covers every cable route at least once.(4)
(Total for Question 19 is 7 marks)
20
When solving a route inspection (Chinese postman) problem, a pair of odd vertices that are not directly joined by an arc must be joined using the shortest path between them in the network, not simply any path. Explain why this is important for finding the shortest possible inspection route.
(Total for Question 20 is 2 marks)
21
A sales representative must visit five client sites, G, H, I, J, K, and return to the starting site. The distances between each pair of sites (in miles, every pair directly connected) are: GH=9, GI=14, GJ=21, GK=17, HI=8, HJ=13, HK=19, IJ=10, IK=16, JK=7.
(a)Apply the nearest neighbour algorithm, starting at G, to find a tour of all five sites, and state its length.(3)
(b)Apply the nearest neighbour algorithm again, this time starting at J, and state the length of the tour found.(3)
(c)Explain why starting the nearest neighbour algorithm at a different vertex can give a tour of a different length.(2)
(d)By deleting site G and finding a minimum spanning tree for the remaining network of H, I, J, K, find a lower bound for the length of the optimal tour.(4)
(e)State the tightest range within which the length of the optimal tour must lie, using your results from parts (a) to (d).(1)
(Total for Question 21 is 13 marks)
22
A driver must plan a tour visiting four towns, Marchford (M), Cavendish (C), Elton (E) and Brindle (B), before returning to the start. The distances between each pair of towns (in miles, every pair directly connected) are: MC=150, MB=320, ME=405, CE=380, CB=245, EB=210.
(a)By deleting town M and finding a minimum spanning tree for the remaining network of C, E, B, find a lower bound for the length of the optimal tour.(4)
(b)Apply the nearest neighbour algorithm, starting at M, to find an upper bound for the length of the optimal tour.(3)
(c)There are only three distinct routes that visit each town once and return to M. List all three routes and find the length of each. Hence state the length of the optimal tour.(4)
(d)Verify that the length of the optimal tour found in part (c) lies within the bounds found in parts (a) and (b).(2)
(Total for Question 22 is 13 marks)
23
A network of junctions used by a fleet of delivery vans is modelled by the vertices A, B, C, D, E, F, G. The arcs represent direct roads between junctions, and their weights are journey times, in minutes: AB = 6, AC = 4, AD = 9, BC = 2, BE = 7, CD = 3, CE = 5, CF = 8, DF = 4, EF = 1, EG = 6, FG = 3.
(a)State the rule used to decide which temporarily labelled vertex is made permanent at each stage of Dijkstra's algorithm.(1)
(b)Use Dijkstra's algorithm, starting at A, to find the shortest time from junction A to junction G. Show the order in which each vertex is permanently labelled, and the working values considered.(6)
(c)State the shortest route from A to G, and the time it takes.(2)
(d)State the shortest route from A to F, and the time it takes.(2)
(e)The council is considering closing the direct road CF for resurfacing. Explain, with reference to your working in part (b), whether this would change the shortest route (and its time) from A to G.(2)
(Total for Question 23 is 13 marks)
24
A parks officer, Connor, needs to check every path in Elmswood Park, shown in the network below, starting and finishing at the main gate (A). The vertices A, B, C, D, E, F represent the path junctions, and the arcs (lengths in metres) are: AB = 4, AC = 6, AD = 5, BC = 3, BE = 7, CD = 2, CF = 8, DE = 4, DF = 6, EF = 5.
Diagram NOT accurately drawn
ABCDEF4653728465
(a)Write down the four vertices of odd degree in this network.(1)
(b)Find the length of the shortest path between each of the following pairs of vertices, showing enough working to justify each answer: A and B; A and E; A and F; B and E; B and F; E and F.(5)
(c)Hence list the three possible ways of pairing the four odd vertices A, B, E, F into two pairs, and find the total length of each pairing.(3)
(d)State which pairing gives the minimum extra distance, and hence find the length of the shortest route, starting and finishing at A, that covers every path in the park at least once.(2)
(e)State which two paths Connor must walk along twice during this shortest route.(1)
(Total for Question 24 is 12 marks)
25
A distribution company must plan a route that visits five depots, V, W, X, Y, Z, and returns to its starting point. The distances between each pair of depots (in miles, every pair directly connected) are: VW=12, VX=18, VY=22, VZ=15, WX=10, WY=16, WZ=20, XY=14, XZ=19, YZ=11.
(a)Explain why applying the nearest neighbour algorithm to this network does not necessarily give the shortest possible route (the optimal tour).(2)
(b)By deleting depot V and finding a minimum spanning tree for the remaining network of W, X, Y, Z, find a lower bound for the length of the optimal tour.(5)
(c)Apply the nearest neighbour algorithm, starting at depot V, to find an upper bound for the length of the optimal tour.(3)
(d)Hence state the length of the optimal tour, giving a reason for your answer, and state a route that achieves this length.(3)
(Total for Question 25 is 13 marks)
26
Elmswood Park has the same path network as in Question 24: vertices A, B, C, D, E, F with arcs (lengths in m) AB=4, AC=6, AD=5, BC=3, BE=7, CD=2, CF=8, DE=4, DF=6, EF=5. Path AC is now closed for resurfacing, so it is not available for Connor's inspection route.
Diagram NOT accurately drawn
ABCDEF453728465
(a)State the new set of vertices of odd degree in the network once path AC is removed.(1)
(b)Find the length of the shortest path between each of the following pairs, using only the remaining paths: B and C; B and E; B and F; C and E; C and F; E and F.(4)
(c)Hence find the three possible pairings of the odd vertices B, C, E, F into two pairs, and the total length of each. State which pairing is optimal, and find the length of the shortest route, starting and finishing at A, that covers every remaining path at least once.(4)
(Total for Question 26 is 9 marks)
Mark scheme · 4.3 Decision Maths: Shortest Paths and Route Inspection

Question 1

  • (a) it does not guarantee that the tour found is optimal (the shortest possible); e.g. a poor early choice can force an expensive arc later in the tour (oe)B1
  • (a) Answer: It does not guarantee an optimal tour, as shown in Question 21 where the tour length depended on the starting vertex.
  • (b) it is much quicker to apply, since an exhaustive search of all routes becomes impractical as the number of vertices increases, because the number of distinct tours grows very rapidly (oe)B1
  • (b) Answer: It is far quicker to apply than checking every possible tour, which becomes impractical for large networks as the number of tours grows very rapidly.
  • (c) the minimum spanning tree found depends on which vertex is deleted, since a different set of remaining vertices (and hence a different remaining network) is used to find the tree; the two least-weight arcs added back also depend on which vertex was deleted, so both parts of the calculation can change, potentially giving a different lower bound total (oe)B1
  • (c) Answer: Both the minimum spanning tree of the remaining vertices and the two cheapest arcs reintroduced depend on which vertex is deleted, so a different deleted vertex can give a different lower bound.

Question 2

  • (a) finds the degree of every vertexM1
  • (a) the odd vertices are B, C, D, EA1
  • (a) Answer: B, C, D, E
  • (b) finds the shortest path for each pair of odd vertices: BC = 19, BD = 21, BE = 23, CD = 22, CE = 4, DE = 26M1
  • (b) totals the weight of each of the three pairings and compares themM1
  • (b) optimal pairing BD, CE with extra weight 25A1
  • (b) Answer: repeat BD, CE, extra weight 25
  • (c) total weight of the network plus the extra weightM1
  • (c) 227 + 25 = 252A1
  • (c) Answer: 252

Question 3

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), C (7), E (12), G (13), B (30), D (32), F (36)A1
  • (a) Answer: A (0), C (7), E (12), G (13), B (30), D (32), F (36)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route AG, length 13A1
  • (b) Answer: AG, length 13

Question 4

  • (a) finds the degree of every vertexM1
  • (a) the odd vertices are A, B, C, GA1
  • (a) Answer: A, B, C, G
  • (b) finds the shortest path for each pair of odd vertices: AB = 14, AC = 9, AG = 34, BC = 21, BG = 32, CG = 41M1
  • (b) totals the weight of each of the three pairings and compares themM1
  • (b) optimal pairing AC, BG, repeating AD, DC, BF and FG with extra weight 5 + 4 + 6 + 26 = 41A1
  • (b) Answer: repeat AD, DC, BF and FG, extra weight 5 + 4 + 6 + 26 = 41
  • (c) total weight of the network plus the extra weightM1
  • (c) 163 + 41 = 204A1
  • (c) Answer: 204

Question 5

  • (a) finds the degree of every vertexM1
  • (a) the odd vertices are A, B, C, FA1
  • (a) Answer: A, B, C, F
  • (b) finds the shortest path for each pair of odd vertices: AB = 35, AC = 45, AF = 19, BC = 53, BF = 27, CF = 26M1
  • (b) totals the weight of each of the three pairings and compares themM1
  • (b) optimal pairing AB, CF, repeating AD, DB and CF with extra weight 24 + 11 + 26 = 61A1
  • (b) Answer: repeat AD, DB and CF, extra weight 24 + 11 + 26 = 61
  • (c) total weight of the network plus the extra weightM1
  • (c) 234 + 61 = 295A1
  • (c) Answer: 295

Question 6

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), D (15), G (20), B (29), E (31), C (36), F (42)A1
  • (a) Answer: A (0), D (15), G (20), B (29), E (31), C (36), F (42)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route AG, length 20A1
  • (b) Answer: AG, length 20

Question 7

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), C (2), E (6), D (18), F (19), B (21), G (32)A1
  • (a) Answer: A (0), C (2), E (6), D (18), F (19), B (21), G (32)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route AG, length 32A1
  • (b) Answer: AG, length 32

Question 8

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), C (3), D (11), B (13), F (21), E (28), G (30)A1
  • (a) Answer: A (0), C (3), D (11), B (13), F (21), E (28), G (30)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route ACEG, length 30A1
  • (b) Answer: ACEG, length 30

Question 9

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), C (17), F (21), B (25), E (33), D (43)A1
  • (a) Answer: A (0), C (17), F (21), B (25), E (33), D (43)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route AF, length 21A1
  • (b) Answer: AF, length 21

Question 10

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), F (3), C (8), E (14), D (18), B (34)A1
  • (a) Answer: A (0), F (3), C (8), E (14), D (18), B (34)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route AF, length 3A1
  • (b) Answer: AF, length 3

Question 11

  • (a) finds the degree of every vertexM1
  • (a) the odd vertices are A, DA1
  • (a) Answer: A, D
  • (b) finds the shortest path A-C-D between the odd vertices: AD = 18 + 22 = 40M1
  • (b) repeats AC and CD with extra weight 40A1
  • (b) Answer: repeat AC and CD, extra weight 18 + 22 = 40
  • (c) total weight of the network plus the extra weightM1
  • (c) 175 + 40 = 215A1
  • (c) Answer: 215

Question 12

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), C (2), E (3), F (19), D (20), B (34)A1
  • (a) Answer: A (0), C (2), E (3), F (19), D (20), B (34)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route ACF, length 19A1
  • (b) Answer: ACF, length 19

Question 13

  • (a) finds the degree of every vertexM1
  • (a) the odd vertices are A, BA1
  • (a) Answer: A, B
  • (b) finds the shortest path for each pair of odd vertices: AB = 39M1
  • (b) optimal pairing AB with extra weight 39A1
  • (b) Answer: repeat AB, extra weight 39
  • (c) total weight of the network plus the extra weightM1
  • (c) 175 + 39 = 214A1
  • (c) Answer: 214

Question 14

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), D (13), C (15), B (25), F (33), E (52)A1
  • (a) Answer: A (0), D (13), C (15), B (25), F (33), E (52)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route ADF, length 33A1
  • (b) Answer: ADF, length 33

Question 15

  • (a) 101 caoB1
  • (a) Answer: 101
  • (b) the only two paths from A to D are A-B-D (length 101) and A-C-D (length 2 + 2 = 4)M1
  • (b) 4 caoA1
  • (b) Answer: Shortest path: A-C-D, length 4.
  • (c) applying the greedy rule at A, the arc of least weight is AB ( = 1), which is smaller than AC ( = 2), so the rule moves to B first (oe)B1
  • (c) from B the only available arc is BD ( = 100), forcing a total length of 101, far more than the true shortest path of length 4 found in part (b), so choosing the locally cheapest arc at each step does not guarantee the overall shortest path (oe)B1
  • (c) Answer: The greedy rule picks AB (weight 1) first since it is cheaper than AC (weight 2), but this forces the expensive arc BD ( = 100), giving 101, not the true shortest path of 4.

Question 16

  • (a) finds the degree of every vertexM1
  • (a) the odd vertices are C, FA1
  • (a) Answer: C, F
  • (b) finds the shortest path C-A-G-D-F between the odd vertices: CF = 5 + 15 + 4 + 14 = 38M1
  • (b) repeats CA, AG, GD and DF with extra weight 38A1
  • (b) Answer: repeat CA, AG, GD and DF, extra weight 5 + 15 + 4 + 14 = 38
  • (c) total weight of the network plus the extra weightM1
  • (c) 165 + 38 = 203A1
  • (c) Answer: 203

Question 17

  • (a) labels A with 0 and updates the working values of its neighboursM1
  • (a) repeatedly makes permanent the vertex with the smallest working value and updates its neighboursM1
  • (a) final labels: A (0), G (11), D (19), F (20), C (29), B (36), E (52)A1
  • (a) Answer: A (0), G (11), D (19), F (20), C (29), B (36), E (52)
  • (b) traces back from the end vertex through the labelsM1
  • (b) route AG, length 11A1
  • (b) Answer: AG, length 11

Question 18

  • (a) finds the degree of every vertexM1
  • (a) the odd vertices are A, EA1
  • (a) Answer: A, E
  • (b) finds the shortest path for each pair of odd vertices: AE = 38M1
  • (b) optimal pairing AE with extra weight 38A1
  • (b) Answer: repeat AE, extra weight 38
  • (c) total weight of the network plus the extra weightM1
  • (c) 266 + 38 = 304A1
  • (c) Answer: 304

Question 19

  • (a) degrees found: P = 2, Q = 3, R = 4, S = 3, T = 2, so Q and S are the only two vertices of odd degree (oe)B1
  • (a) a network with exactly two vertices of odd degree has a route using every arc exactly once, provided it starts at one odd vertex and finishes at the other (oe)B1
  • (a) total length = 3 + 4 + 2 + 5 + 6 + 7 + 1 = 28 (km) caoB1
  • (a) Answer: Q and S are the only odd vertices, so a route exists from Q to S using every arc exactly once, of length 28 km.
  • (b) for a closed route (same start and finish), every vertex must have even degree, so the two odd vertices, Q and S, must be paired using the shortest path between themM1
  • (b) shortest path Q to S: direct QS = 5, compared with Q-R-S = 2 + 6 = 8, so shortest = 5 (km)A1
  • (b) extra distance = 5 (the length of the repeated path)M1
  • (b) length of shortest closed route = 28 + 5 = 33 (km) caoA1
  • (b) Answer: Extra distance = 5 km; shortest closed route (start/finish at P) = 33 km.

Question 20

  • the extra (repeated) distance added to the route equals the length of the path used to join the pair, so a longer path than necessary would add more extra distance than needed (oe)B1
  • using the shortest path between the pair minimises the total extra distance added, and hence minimises the total length of the inspection route (oe)B1
  • Answer: Because the extra distance walked equals the length of the joining path, using anything other than the shortest path would add more distance than necessary, so the shortest path must be used to minimise the total route length.

Question 21

  • (a) from G, nearest unvisited is H (9); from H, nearest unvisited is I (8); from I, nearest unvisited is J (10)M1
  • (a) from J, only K remains (7); return from K to G (17); tour: G-H-I-J-K-GA1
  • (a) length = 9+8+10+7+17 = 51 (miles) caoA1
  • (a) Answer: Tour G-H-I-J-K-G, length 51 miles.
  • (b) from J, nearest unvisited is K (7); from K, nearest unvisited is I (16)M1
  • (b) from I, nearest unvisited is H (8); from H, only G remains (9); return from G to J (21); tour: J-K-I-H-G-JA1
  • (b) length = 7+16+8+9+21 = 61 (miles) caoA1
  • (b) Answer: Tour J-K-I-H-G-J, length 61 miles.
  • (c) the algorithm's choices depend entirely on which arcs are cheapest from the current site, so a different starting site leads to a different sequence of 'nearest unvisited' choices being made (oe)B1
  • (c) in part (b), starting at J forces an expensive arc back to J at the end (GJ=21), whereas starting at G in part (a) allows this expensive arc to be avoided altogether, giving a shorter tour (oe)B1
  • (c) Answer: The algorithm's greedy choices depend on the start vertex; different starts avoid or incur different 'expensive' arcs, especially the final return arc, giving tours of different lengths (51 versus 61 here).
  • (d) network on H,I,J,K has arcs HI=8, HJ=13, HK=19, IJ=10, IK=16, JK=7; sorted ascending: JK(7), HI(8), IJ(10), HJ(13), IK(16), HK(19)M1
  • (d) JK accepted (7); HI accepted (8); IJ accepted (10), connecting the two parts into a single tree; minimum spanning tree weight = 7+8+10 = 25M1
  • (d) two least-weight arcs from G are added: GH=9 and GI=14 (the two smallest of GH=9, GI=14, GJ=21, GK=17)A1
  • (d) lower bound = 25 + 9 + 14 = 48 (miles) caoA1
  • (d) Answer: Lower bound = 48 miles.
  • (e) 48 ≤ length of optimal tour ≤ 51, using the lower bound of 48 from part (d) and the best tour found, 51, from part (a) caoB1
  • (e) Answer: 48 to 51 miles (inclusive).

Question 22

  • (a) network on C,E,B has arcs CE=380, EB=210, CB=245; sorted ascending: EB(210), CB(245), CE(380)M1
  • (a) EB accepted (210); CB accepted (245), connecting all of C, E, B with 2 edges (CE not needed, and would form a cycle); minimum spanning tree weight = 210+245 = 455M1
  • (a) two least-weight arcs from M are added: MC=150 and MB=320 (the two smallest of MC=150, MB=320, ME=405)A1
  • (a) lower bound = 455 + 150 + 320 = 925 (miles) caoA1
  • (a) Answer: Lower bound = 925 miles.
  • (b) from M, nearest unvisited is C (150); from C, nearest unvisited is B (245, compared with CE=380)M1
  • (b) from B, only E remains (210); return from E to M (405); tour: M-C-B-E-MA1
  • (b) length = 150+245+210+405 = 1010 (miles) caoA1
  • (b) Answer: Upper bound = 1010 miles (tour M-C-B-E-M).
  • (c) Route 1: M-C-E-B-M = 150+380+210+320 = 1060M1
  • (c) Route 2: M-C-B-E-M = 150+245+210+405 = 1010M1
  • (c) Route 3: M-E-C-B-M = 405+380+245+320 = 1350A1
  • (c) optimal tour = Route 2, M-C-B-E-M, length 1010 (miles), the shortest of the three caoA1
  • (c) Answer: Optimal tour: M-C-B-E-M, length 1010 miles.
  • (d) 925 (lower bound, part (a)) ≤ 1010 (optimal tour, part (c))B1
  • (d) 1010 (optimal tour, part (c)) ≤ 1010 (upper bound, part (b)); in fact the nearest neighbour tour found in part (b) is itself the optimal tour here caoB1
  • (d) Answer: 925 ≤ 1010 ≤ 1010, so the optimal tour does lie within the bounds; here the upper bound found by nearest neighbour is exactly optimal.

Question 23

  • (a) the temporarily labelled vertex with the smallest working value is made permanent at each stage (oe)B1
  • (a) Answer: The vertex with the smallest current working value is selected and made permanent.
  • (b) A permanently labelled with 0; initial working values B = 6 (via A), C = 4 (via A), D = 9 (via A)M1
  • (b) C permanently labelled second, with value 4; D updated to 7 (via C, since 4 + 3 = 7 < 9), E = 9 (via C), F = 12 (via C); B unchanged at 6 (4 + 2 = 6 is not an improvement)M1
  • (b) B permanently labelled third, with value 6 (via A); no improving updates result from BM1
  • (b) D permanently labelled fourth, with value 7 (via C); F updated to 11 (via D, since 7 + 4 = 11 < 12)M1
  • (b) E permanently labelled fifth, with value 9 (via C); F updated to 10 (via E, since 9 + 1 = 10 < 11), G = 15 (via E)A1
  • (b) F permanently labelled sixth, with value 10 (via E); G updated to 13 (via F, since 10 + 3 = 13 < 15); G permanently labelled seventh (last) at 13; full order stated as A, C, B, D, E, F, GA1
  • (b) Answer: Order of permanent labelling: A(0), C(4), B(6), D(7), E(9), F(10), G(13).
  • (c) A-C-E-F-G (oe, traced back through predecessors from G)B1
  • (c) 13 (minutes) caoB1
  • (c) Answer: A-C-E-F-G, 13 minutes.
  • (d) A-C-E-F (oe, traced back through predecessors from F)B1
  • (d) 10 (minutes) caoB1
  • (d) Answer: A-C-E-F, 10 minutes.
  • (e) correct conclusion: no change results (oe)B1
  • (e) valid justification, e.g. F's temporary value of 12 obtained via CF was superseded first by 11 (via D) and then by 10 (via E), so arc CF was never used to obtain F's final permanent label, or any part of the shortest route to G (oe)B1
  • (e) Answer: No change; the shortest route already avoids arc CF.

Question 24

  • (a) A, B, E, F caoB1
  • (a) Answer: A, B, E, F.
  • (b) AB = 4 (direct arc; no shorter route is available)M1
  • (b) AE: A-D-E = 5+4 = 9 (compared with A-B-E = 4+7 = 11 and A-C-D-E = 6+2+4 = 12); shortest = 9M1
  • (b) AF: A-D-F = 5+6 = 11 (compared with A-C-F = 6+8 = 14 and A-D-E-F = 5+4+5 = 14); shortest = 11M1
  • (b) BE = 7 (direct arc, compared with B-C-D-E = 3+2+4 = 9); EF = 5 (direct arc, compared with E-D-F = 4+6 = 10)A1
  • (b) BF: B-C-F = 3+8 = 11 (equal to B-C-D-F = 3+2+6 = 11); shortest = 11A1
  • (b) Answer: AB=4, AE=9, AF=11, BE=7, BF=11, EF=5.
  • (c) (AB and EF): 4 + 5 = 9B1
  • (c) (AE and BF): 9 + 11 = 20B1
  • (c) (AF and BE): 11 + 7 = 18B1
  • (c) Answer: Pairing totals: (AB,EF)=9; (AE,BF)=20; (AF,BE)=18.
  • (d) pairing (AB and EF), extra distance = 9, is the minimum (since 9 < 18 < 20)B1
  • (d) total length of network (4+6+5+3+7+2+8+4+6+5 = 50) plus 9 gives 59 (m) caoB1
  • (d) Answer: Minimum pairing: AB and EF (extra = 9); shortest route length = 59 m.
  • (e) AB and EF (the two arcs identified in the minimum pairing in part (d))B1
  • (e) Answer: AB and EF.

Question 25

  • (a) the nearest neighbour algorithm only ever chooses the cheapest available arc from the current depot, without considering the effect this choice has on the arcs that will be forced later in the tour (a 'greedy' choice) (oe)B1
  • (a) an early cheap choice can leave only expensive arcs available later in the tour, so the total may not be minimal; a different, locally more expensive choice might allow cheaper arcs to be used later, giving a shorter overall tour (oe)B1
  • (a) Answer: The algorithm makes locally cheapest choices without considering later consequences, so an early cheap arc can force expensive arcs later, giving a total that is not necessarily minimal.
  • (b) network on W,X,Y,Z has arcs WX=10, WY=16, WZ=20, XY=14, XZ=19, YZ=11; sorted ascending: WX(10), YZ(11), XY(14), WY(16), XZ(19), WZ(20)M1
  • (b) WX accepted (10); YZ accepted (11); XY accepted (14), connecting the two parts into a single tree of 3 edgesM1
  • (b) minimum spanning tree = {WX, YZ, XY}, weight = 10+11+14 = 35A1
  • (b) the two least-weight arcs from V are added back: VW=12 and VZ=15 (the two smallest of VW=12, VX=18, VY=22, VZ=15)M1
  • (b) lower bound = 35 + 12 + 15 = 62 (miles) caoA1
  • (b) Answer: Lower bound = 62 miles.
  • (c) from V, nearest unvisited depot is W (12); from W, nearest unvisited is X (10); from X, nearest unvisited is Y (14)M1
  • (c) from Y, only Z remains (11); return from Z to V (15); tour: V-W-X-Y-Z-VM1
  • (c) length = 12+10+14+11+15 = 62 (miles) caoA1
  • (c) Answer: Upper bound = 62 miles (tour V-W-X-Y-Z-V).
  • (d) since the lower bound (62) equals the upper bound (62), the length of the optimal tour must be exactly 62 miles (oe)B1
  • (d) reason: the true optimal tour length can never be less than the lower bound, nor more than the length of any actual tour found; so if these two values coincide, that common value must be the optimal length (oe)B1
  • (d) route achieving this length: V-W-X-Y-Z-V (or its reverse) caoB1
  • (d) Answer: Optimal tour length = 62 miles, achieved by V-W-X-Y-Z-V.

Question 26

  • (a) B, C, E, F caoB1
  • (a) Answer: B, C, E, F.
  • (b) BC = 3 (direct arc); BE = 7 (direct arc)M1
  • (b) BF: B-C-F = 3+8 = 11 (equal to B-C-D-F = 3+2+6 = 11); shortest = 11M1
  • (b) CE: C-D-E = 2+4 = 6 (there is no direct CE arc); CF = 8 (direct arc, equal to C-D-F = 2+6 = 8)M1
  • (b) EF = 5 (direct arc)A1
  • (b) Answer: BC=3, BE=7, BF=11, CE=6, CF=8, EF=5.
  • (c) (BC and EF): 3 + 5 = 8M1
  • (c) (BE and CF): 7 + 8 = 15M1
  • (c) (BF and CE): 11 + 6 = 17; minimum pairing is (BC, EF) = 8A1
  • (c) sum of remaining arcs = 50 - 6 = 44 (since AC = 6 is removed); shortest route = 44 + 8 = 52 (m) caoA1
  • (c) Answer: Minimum pairing: BC and EF (extra = 8); shortest route = 52 m.

Mark your answers

Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.

Question 1

3 marks
Did your answer earn the marks?

Question 2

7 marks
Did your answer earn the marks?

Question 3

5 marks
Did your answer earn the marks?

Question 4

7 marks
Did your answer earn the marks?

Question 5

7 marks
Did your answer earn the marks?

Question 6

5 marks
Did your answer earn the marks?

Question 7

5 marks
Did your answer earn the marks?

Question 8

5 marks
Did your answer earn the marks?

Question 9

5 marks
Did your answer earn the marks?

Question 10

5 marks
Did your answer earn the marks?

Question 11

6 marks
Did your answer earn the marks?

Question 12

5 marks
Did your answer earn the marks?

Question 13

6 marks
Did your answer earn the marks?

Question 14

5 marks
Did your answer earn the marks?

Question 15

5 marks
Did your answer earn the marks?

Question 16

6 marks
Did your answer earn the marks?

Question 17

5 marks
Did your answer earn the marks?

Question 18

6 marks
Did your answer earn the marks?

Question 19

7 marks
Did your answer earn the marks?

Question 20

2 marks
Did your answer earn the marks?

Question 21

13 marks
Did your answer earn the marks?

Question 22

13 marks
Did your answer earn the marks?

Question 23

13 marks
Did your answer earn the marks?

Question 24

12 marks
Did your answer earn the marks?

Question 25

13 marks
Did your answer earn the marks?

Question 26

9 marks
Did your answer earn the marks?
Mark my answers

Worksheets are written for Revision Library and come with a full mark scheme; a few English packs quote an out-of-copyright text, and name it on the page. Exam board names and specification codes say which qualification a pack suits: we are not affiliated with, endorsed by or approved by any exam board, and no past-paper question is reproduced here. Rights queries: hello@revisionlibrary.co.uk