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.
Decision Maths: Shortest Paths and Route Inspection revision guideMore A Level Further Maths practiceMock exams
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.
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.