Algorithms on graphs
D1 Topic 2, spec point by spec point (Algorithms on graphs). Each spec point has the method, worked examples written the way the mark scheme wants them, how the marks go and the mistakes that cost the most marks.
Spec2.1Minimum spanning trees: Prim's and Kruskal's algorithms
The minimum spanning tree (minimum connector) problem, using Prim's and Kruskal's algorithms. Matrix representation for Prim's algorithm is expected, as is drawing a network from a matrix and writing the matrix for a network.
The vocabulary
- A tree is a connected graph with no cycles. With \(n\) vertices it has \(n - 1\) arcs.
- A spanning tree connects every vertex of a network.
- A minimum spanning tree (MST) is a spanning tree with the smallest total weight. Use: connecting places as cheaply as possible (cables, pipes, roads).
Kruskal's algorithm
- List the arcs in order of weight, smallest first.
- Add each arc in turn unless it makes a cycle (then reject it and say so).
- Stop when you have \(n - 1\) arcs.
Prim's algorithm
- Start at any vertex (the question will usually say which).
- Add the shortest arc joining a vertex in the tree to a vertex not yet in the tree.
- Repeat until every vertex is in the tree.
Prim never needs to check for cycles, because it only ever joins a new vertex.
Prim's algorithm on a matrix
- Choose the start vertex. Delete its row and number its column 1.
- Look down all numbered columns for the smallest undeleted entry. Circle it: that arc joins the new vertex (its row).
- Delete that new vertex's row and number its column with the next number.
- Repeat until every column is numbered.
Kruskal and Prim on a network
Arcs: AB 7, AC 5, AD 9, BC 4, BE 8, CD 6, CE 11, DF 11, EF 3.
Kruskal: EF 3 ✓, BC 4 ✓, AC 5 ✓, CD 6 ✓, AB 7 ✗ (cycle ABC), BE 8 ✓. That's 5 arcs for 6 vertices, so stop. Weight 26.
Prim from A: AC 5, CB 4, CD 6, BE 8, EF 3. Same tree, weight 26.
Prim's on a matrix
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | – | 12 | 20 | 15 | 18 |
| B | 12 | – | 10 | 17 | 24 |
| C | 20 | 10 | – | 14 | 16 |
| D | 15 | 17 | 14 | – | 11 |
| E | 18 | 24 | 16 | 11 | – |
Start at A: delete row A, number column A.
Smallest in column A: 12 (row B). Arc AB. Delete row B, number column B.
Smallest in columns A and B: 10 (row C). Arc BC. Delete row C, number column C.
Smallest in columns A, B, C: 14 (row D). Arc CD. Then 11 (row E): arc DE.
Order: AB, BC, CD, DE. Weight 47.
- Prim: M1 for the first few arcs (or vertices) in the right order, A1 for more, A1 cso for all arcs in order. Weights alone are not accepted; showing rejections or starting elsewhere limits you to M1 (WDM11A Jan 2026 Q2a, WDM11 Jan 2023 Q11c).
- Kruskal: the arcs in order with rejections shown at the right points.
- Algebraic versions: if Prim from A picks AB first, then AB is lighter than every other arc at A, which gives inequalities in \(x\) and \(y\) (WDM11 Jun 2021 Q7b).
Often asked as: very common (40 questions). Apply Prim (often on a matrix) or Kruskal; state the weight; draw the tree; explain the difference between the two.
Listing arcs without the order.
Using Kruskal's method when Prim's was asked (or the reverse).
In Prim, choosing the shortest arc from the latest vertex only rather than from the whole tree.
Spec2.2Dijkstra's algorithm
Dijkstra's algorithm for finding the shortest path.
The idea
Dijkstra finds the shortest route from a start vertex to every other vertex by permanently labelling vertices in order of their distance from the start.
The labelling boxes
Each vertex gets a box: vertex | order labelled | final value, with a row of working values underneath.
Method
- Give the start vertex final value 0, order 1.
- For each vertex joined to the vertex just labelled, work out (its final value + arc weight). Write this as a working value if it's smaller than the vertex's current working value (or if it has none). Never cross out a smaller value with a larger one.
- Among all vertices without a final label, choose the smallest working value. Make it final and give it the next order number.
- Repeat steps 2 and 3 until the destination is labelled.
- Trace back the route: from the end, step back along an arc whose weight equals the difference between the two final values.
shortest route from A to F
Arcs: AB 7, AC 5, AD 9, BC 4, BE 8, CD 6, CE 11, DF 11, EF 3.
| Vertex | Order | Final | Working values |
|---|---|---|---|
| A | 1 | 0 | 0 |
| C | 2 | 5 | 5 |
| B | 3 | 7 | 7 |
| D | 4 | 9 | 9 |
| E | 5 | 15 | 16, 15 |
| F | 6 | 18 | 20, 18 |
After labelling C, E gets 16 (via C). After labelling B, E gets 15 (via B), which replaces 16. F gets 20 via D, then 18 via E.
Trace back: \(18 - 3 = 15\) (E), \(15 - 8 = 7\) (B), \(7 - 7 = 0\) (A). Route ABEF, length 18.
- M1 for a larger working value replaced by a smaller one at least twice; A1 for the first few vertices with working values in the right order; A1 for more; A1ft for the last; A1 for the route and length (WDM11A Jan 2026 Q3a).
- The order of the working values and of the labelling must be strictly right (WDM11 Jun 2021 Q5b).
Often asked as: very common (31 questions). Usually 6–8 marks in the answer book's boxes, followed by "state the shortest route" and then a route inspection question on the same network (3.1).
Writing every possible working value, including larger ones.
Labelling the next vertex by its nearest neighbour rather than the smallest working value overall.