AS June 2023 Q3

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)

Notes

In (b) 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 E the working values must be 58 50 in that order (so 50 58 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

M1: A larger working value being replaced by a smaller working value at any two of A, B, E, F, G, J

A1: All values at C, D, B and H correct and the working values in the correct order

A1: All values at G, E and A correct and working values in the correct order. Penalise order of labelling only once per question. Condone an additional working value of 57 after the 39 (but A0 if the 57 appears before either the 41 or 39 at G)

A1ft: 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 B, E, G and J). For example, if correct then the order of labelling of nodes B, G and E are 3, 5 and 6 respectively so the working values at F should come from B, G and E in that order. The first working value at F should be their 30 (the Final value at B) + 58 (the weight of the arc BF), the second working value at F should be their 39 (the Final value at G) + 43 (the weight of the arc GF), the third working value at F should be their 50 (the Final value at E) + 30 (the weight of the arc EF). Repeat the process for J (which will have working values from H, G and F with the order of these nodes determined by the candidate’s order of labelling at H, G and F).

A1: cao for shortest route (A B D C D G E F J) – must be from A to J (and not stated as a route from J to A)

A1ft: Follow through their final value at A + their final value at J only (so do not award this mark for 156 if it doesn’t follow from these two final values)

Special Case in (b) – starting at node A:

For those candidates starting Dijkstra at A (rather than C) the following marks can be awarded in (b):

M1: A larger working value being replaced by a smaller working value at any two of C, D, F, J
A1: All values correct at A, B, E, D and G
A1: All values correct at C, F, H and J
Followed by A0, A0 and A0 (so max. 3 out of 6 in (b))

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

Notes

B1: cao (155) (no units required) – must follow from the correct arcs stated in (c)