| Shortest path: A – D – G – F – J; Length: 28 (miles) | A1, A1 ft | (6) |

**Part (b)**

| Shortest path: J – F – G – D – A – B – C – E – H; Length: 28 + 20 = 48 (miles) | B1, B1 ft | (2) |

**Part (c)**

| $A(BC)E + FG = 15 + 3 = 18^*$ | M1 |  |
| $A(DG)F + E(HF)G = 27 + 16 = 43$ | A1 |  |
| $A(D)G + E(H)F = 24 + 13 = 37$ | A1 |  |
| Repeat arcs: AB, BC, CE, FG | A1 |  |
| Length: 193 + 18 = 211 (miles) | A1 ft | (5) |

**Part (d)**

| EF (13) is the shortest link between two odd nodes excluding G | M1 |  |
| Repeat EF (13) since this is the shortest path excluding G | A1 |  |
| We finish at A | A1 |  |
| Length of route = 193 + 13 = 206 (miles) | A1 | (3) |

| | | (16 marks) |

**Notes for Question 2:**

In (a) it is important that all values at each node are checked very carefully – the order of the working values must be correct for the corresponding A mark to be awarded e.g. at H the working values must be 21 20 in that order (so 20 21 is incorrect).

It is also important that the order of labelling is checked carefully. The order of labelling must be a strictly increasing sequence – so 1, 2, 3, 3, 4, … will be penalised once (see notes below) but 1, 2, 3, 5, 6, … is fine. Errors in the final values and working values are penalised before errors in the order of labelling

**a1M1:** A larger value replaced by a smaller value at least twice in the working values at either E, F, H or J

**a1A1:** All values at B, C, D and F correct and the working values in the correct order

**a3A1ft:** All values in F and J correct on the follow through and the working values in the correct order. To follow through F check that the working values at F follow from the candidate's final values for the nodes that are directly attached to F (which are A, D, E, F, H, G (and J)). For example, if correct then the order of labelling of nodes A, D, H and G are 1, 4, 6 and 7 respectively so the working values at F should come from A, D, H and G in that order. The first working value at F should be 30 (from A), the second working value at F should be their 29 (the Final value at D) + 21 (the weight of the arc DF), the third working value at F should be their 20 (the Final value at H) + 8 (the weight of the arc HF) and the fourth working value at F should be their 24 (the Final value at G) + 3 (the weight of the arc FG). Repeat the process for J (which will have working values from B, H, G and F) with the order of these nodes determined by the candidate's order of labelling at B, H, G and F)

**a4A1:** CAO (ADGFJ or AD, DG, GF, FJ but not JFGDA or equivalent from J to A)

**a5A1ft:** Follow through their final value at J only – if their answer is 28 but this is not the Final Value at J then A0

**b1B1:** CAO for the route (JFGDABCEH or JF, FG, GD, DA, AB, BC, CE, EH)

**b2B1ft:** 48 or follow through their final value at J + their final value at H

**c1M1:** Three distinct pairings of the nodes A, E, F and G

**c1A1:** Any two rows correct including pairings and totals

**c2A1:** All three rows correct including pairings and totals

**c3A1:** CAO - correct arcs clearly stated and not just in their working as AB, BC, CE and FG (allow BA, CB, etc.) – must be these arcs. Do not accept ABCE or AE via B and C

**c4A1 ft:** Correct answer of 211 or follow through 193 + their least total from a choice of three

**d1M1:** Identifies the need to repeat one path of the three (AE, AF, EF) which does not include G (maybe implicit) or listing of only these possible repeats – this mark is dependent on either scoring the M mark in (c) or stating all three possible paths. If stating more than these three paths then it must be clear from later working that they are only considering these three. As a minimum stating just one of these three paths (or any combination of these three paths with no others) can score this mark (so, for example, just stating AE and AF scores this mark) provided that they do not imply that a path including G should be repeated (as this would indicate that mentioning one (or more) of these paths is for the purpose of not repeating it)

**d1A1:** Identifies EF as the least and A as the finishing point. They have to explicitly state that EF is the least path that does not include G

**d2A1:** CAO (206)

---