Revision Library

revisionlibrary.co.uk

A-Level · AQA

FP.D3 Decision Maths: Shortest Paths and Route Inspection

AQA 7367 · Calculator allowed · about 145 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

The network below shows the cycle paths connecting five villages: Ashfield (A), Barrowby (B), Cotgrave (C), Denwick (D) and Elsdon (E). The number on each arc is the length of that path, in km: AB = 4, AC = 2, BC = 1, BD = 5, CD = 8, CE = 10, DE = 2.

(a)State one condition on the arc weights of a network that Dijkstra's algorithm requires in order to be guaranteed to find the shortest path.(1)

(b)Use Dijkstra's algorithm, starting at A, to find the shortest path from A to E. Show clearly the order in which each vertex receives its permanent label, and the working values considered at each stage.(5)

(c)Hence state the shortest path from A to E, and its length.(2)

(Total for Question 1 is 8 marks)

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 2 is 13 marks)

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).

(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 3 is 5 marks)

A one-way road system linking a supermarket's warehouse (S) to a delivery hub (T) is modelled by a directed network with vertices S, A, B, C, T. Every arc may only be travelled in the direction stated: S to A = 5, S to B = 9, A to B = 2, A to C = 6, B to C = 1, B to T = 7, C to T = 3 (weights are journey times, in minutes; there is no arc in the reverse direction unless separately listed).

(a)Explain why the direction of each arc must be taken into account when applying Dijkstra's algorithm to this network.(1)

(b)Use Dijkstra's algorithm on this directed network, starting at S, to find the shortest time from S to T. Show the order in which each vertex is permanently labelled and the working values considered.(6)

(c)State the shortest route from S to T, and the time it takes.(2)

(d)Verify that the shortest route found in part (c) does not use the direct arc from S to B, and explain what this shows about B's permanent label.(2)

(Total for Question 4 is 11 marks)

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.

(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 5 is 7 marks)

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.

(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 6 is 12 marks)

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 7 is 2 marks)

Elmswood Park has the same path network as in Question 6: 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.

(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 8 is 9 marks)

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 9 is 13 marks)

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 10 is 13 marks)

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 11 is 3 marks)

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 12 is 13 marks)

Mark scheme · FP.D3 Decision Maths: Shortest Paths and Route Inspection

Question 1

(a) B1 all arc weights (lengths) must be non-negative (oe)
(a) Answer: All arc weights must be non-negative.
(b) M1 A permanently labelled with 0; working values found: B = 4 (via A), C = 2 (via A)
(b) M1 C permanently labelled second, with value 2; B updated to 3 (via C, since 2 + 1 = 3 < 4), D = 10 (via C), E = 12 (via C)
(b) M1 B permanently labelled third, with value 3; D updated to 8 (via B, since 3 + 5 = 8 < 10)
(b) A1 D permanently labelled fourth, with value 8; E updated to 10 (via D, since 8 + 2 = 10 < 12)
(b) A1 E permanently labelled fifth (last), with final value 10; order of labelling correctly stated as A, C, B, D, E
(b) Answer: Order of permanent labelling: A(0), C(2), B(3), D(8), E(10).
(c) B1 A-C-B-D-E (oe, traced back through predecessors from E)
(c) B1 10 (km) cao
(c) Answer: Shortest path: A-C-B-D-E, length 10 km.

Question 2

(a) B1 the temporarily labelled vertex with the smallest working value is made permanent at each stage (oe)
(a) Answer: The vertex with the smallest current working value is selected and made permanent.
(b) M1 A permanently labelled with 0; initial working values B = 6 (via A), C = 4 (via A), D = 9 (via A)
(b) M1 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)
(b) M1 B permanently labelled third, with value 6 (via A); no improving updates result from B
(b) M1 D permanently labelled fourth, with value 7 (via C); F updated to 11 (via D, since 7 + 4 = 11 < 12)
(b) A1 E permanently labelled fifth, with value 9 (via C); F updated to 10 (via E, since 9 + 1 = 10 < 11), G = 15 (via E)
(b) A1 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, G
(b) Answer: Order of permanent labelling: A(0), C(4), B(6), D(7), E(9), F(10), G(13).
(c) B1 A-C-E-F-G (oe, traced back through predecessors from G)
(c) B1 13 (minutes) cao
(c) Answer: A-C-E-F-G, 13 minutes.
(d) B1 A-C-E-F (oe, traced back through predecessors from F)
(d) B1 10 (minutes) cao
(d) Answer: A-C-E-F, 10 minutes.
(e) B1 correct conclusion: no change results (oe)
(e) B1 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)
(e) Answer: No change; the shortest route already avoids arc CF.

Question 3

(a) B1 101 cao
(a) Answer: 101
(b) M1 the only two paths from A to D are A-B-D (length 101) and A-C-D (length 2 + 2 = 4)
(b) A1 4 cao
(b) Answer: Shortest path: A-C-D, length 4.
(c) B1 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)
(c) B1 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)
(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 4

(a) B1 an arc can only be used in the direction shown; a vertex's working value may only be updated using an arc that points towards it, so travelling the 'wrong way' along a one-way arc is not permitted (oe)
(a) Answer: Arcs may only be used in the direction given, so a vertex can only be reached via arcs pointing into it.
(b) M1 S permanently labelled with 0; initial working values A = 5 (via S), B = 9 (via S)
(b) M1 A permanently labelled second, with value 5; B updated to 7 (via A, since 5 + 2 = 7 < 9), C = 11 (via A, since 5 + 6 = 11)
(b) M1 B permanently labelled third, with value 7 (via A); C updated to 8 (via B, since 7 + 1 = 8 < 11)
(b) M1 C permanently labelled fourth, with value 8 (via B); T updated to 11 (via C, since 8 + 3 = 11)
(b) A1 T permanently labelled fifth (last), with value 11
(b) A1 full order of labelling correctly stated as S, A, B, C, T
(b) Answer: Order of permanent labelling: S(0), A(5), B(7), C(8), T(11).
(c) B1 S-A-B-C-T (oe, traced back through predecessors from T)
(c) B1 11 (minutes) cao
(c) Answer: S-A-B-C-T, 11 minutes.
(d) B1 the route S-A-B-C-T uses arc A to B, not the direct arc S to B, so the direct arc SB is not used cao
(d) B1 this shows that B's permanent label of 7 was achieved via A (5 + 2 = 7), which is less than the direct arc's weight of 9, so the direct arc is not always part of the shortest route through a vertex (oe)
(d) Answer: The route uses arc A-B, not S-B directly; B's shortest working value (7, via A) beats the direct arc S-B (9).

Question 5

(a) B1 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)
(a) B1 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)
(a) B1 total length = 3 + 4 + 2 + 5 + 6 + 7 + 1 = 28 (km) cao
(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) M1 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 them
(b) A1 shortest path Q to S: direct QS = 5, compared with Q-R-S = 2 + 6 = 8, so shortest = 5 (km)
(b) M1 extra distance = 5 (the length of the repeated path)
(b) A1 length of shortest closed route = 28 + 5 = 33 (km) cao
(b) Answer: Extra distance = 5 km; shortest closed route (start/finish at P) = 33 km.

Question 6

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

Question 7

B1 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)
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 8

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

Question 9

(a) B1 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)
(a) B1 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)
(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) M1 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)
(b) M1 WX accepted (10); YZ accepted (11); XY accepted (14), connecting the two parts into a single tree of 3 edges
(b) A1 minimum spanning tree = {WX, YZ, XY}, weight = 10+11+14 = 35
(b) M1 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)
(b) A1 lower bound = 35 + 12 + 15 = 62 (miles) cao
(b) Answer: Lower bound = 62 miles.
(c) M1 from V, nearest unvisited depot is W (12); from W, nearest unvisited is X (10); from X, nearest unvisited is Y (14)
(c) M1 from Y, only Z remains (11); return from Z to V (15); tour: V-W-X-Y-Z-V
(c) A1 length = 12+10+14+11+15 = 62 (miles) cao
(c) Answer: Upper bound = 62 miles (tour V-W-X-Y-Z-V).
(d) B1 since the lower bound (62) equals the upper bound (62), the length of the optimal tour must be exactly 62 miles (oe)
(d) B1 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)
(d) B1 route achieving this length: V-W-X-Y-Z-V (or its reverse) cao
(d) Answer: Optimal tour length = 62 miles, achieved by V-W-X-Y-Z-V.

Question 10

(a) M1 from G, nearest unvisited is H (9); from H, nearest unvisited is I (8); from I, nearest unvisited is J (10)
(a) A1 from J, only K remains (7); return from K to G (17); tour: G-H-I-J-K-G
(a) A1 length = 9+8+10+7+17 = 51 (miles) cao
(a) Answer: Tour G-H-I-J-K-G, length 51 miles.
(b) M1 from J, nearest unvisited is K (7); from K, nearest unvisited is I (16)
(b) A1 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-J
(b) A1 length = 7+16+8+9+21 = 61 (miles) cao
(b) Answer: Tour J-K-I-H-G-J, length 61 miles.
(c) B1 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)
(c) B1 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)
(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) M1 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)
(d) M1 JK accepted (7); HI accepted (8); IJ accepted (10), connecting the two parts into a single tree; minimum spanning tree weight = 7+8+10 = 25
(d) A1 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)
(d) A1 lower bound = 25 + 9 + 14 = 48 (miles) cao
(d) Answer: Lower bound = 48 miles.
(e) B1 48 ≤ length of optimal tour ≤ 51, using the lower bound of 48 from part (d) and the best tour found, 51, from part (a) cao
(e) Answer: 48 to 51 miles (inclusive).

Question 11

(a) B1 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)
(a) Answer: It does not guarantee an optimal tour, as shown in Question 10 where the tour length depended on the starting vertex.
(b) B1 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)
(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) B1 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)
(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 12

(a) M1 network on C,E,B has arcs CE=380, EB=210, CB=245; sorted ascending: EB(210), CB(245), CE(380)
(a) M1 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 = 455
(a) A1 two least-weight arcs from M are added: MC=150 and MB=320 (the two smallest of MC=150, MB=320, ME=405)
(a) A1 lower bound = 455 + 150 + 320 = 925 (miles) cao
(a) Answer: Lower bound = 925 miles.
(b) M1 from M, nearest unvisited is C (150); from C, nearest unvisited is B (245, compared with CE=380)
(b) A1 from B, only E remains (210); return from E to M (405); tour: M-C-B-E-M
(b) A1 length = 150+245+210+405 = 1010 (miles) cao
(b) Answer: Upper bound = 1010 miles (tour M-C-B-E-M).
(c) M1 Route 1: M-C-E-B-M = 150+380+210+320 = 1060
(c) M1 Route 2: M-C-B-E-M = 150+245+210+405 = 1010
(c) A1 Route 3: M-E-C-B-M = 405+380+245+320 = 1350
(c) A1 optimal tour = Route 2, M-C-B-E-M, length 1010 (miles), the shortest of the three cao
(c) Answer: Optimal tour: M-C-B-E-M, length 1010 miles.
(d) B1 925 (lower bound, part (a)) ≤ 1010 (optimal tour, part (c))
(d) B1 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 cao
(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.

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