# Algorithms on graphs

> Edexcel International A-Level Mathematics · IAL Maths D1
> Source: https://www.owlsprep.com/study/edexcel-ial-math-d1-algorithms-on-graphs/

This guide teaches you the three core graph algorithms for Edexcel IAL D1: Kruskal's, Prim's (both network and matrix versions), and Dijkstra's. You will work through exam-style examples and learn exactly how to present answers to secure full marks.

**Prerequisites:** [Basic graph terminology (vertices, edges, weights, cycles)](https://www.owlsprep.com/study/edexcel-ial-math-d1-graph-terminology/)

## Learning objectives

- Apply Kruskal's and Prim's algorithms to find minimum spanning trees of weighted networks
- Use adjacency matrix representation to execute Prim's algorithm correctly
- Convert between graph network diagrams and adjacency matrices
- Apply Dijkstra's algorithm to find the shortest path between two vertices in a graph with non-negative weights
- Present ordered edge/vertex selections and working as required for Edexcel exam mark schemes

## Kruskal's Algorithm for Minimum Spanning Trees

**Kruskal's Algorithm** — Greedy algorithm that constructs a minimum spanning tree (MST) by sorting all edges by weight ascending, then adding edges one by one, skipping any edge that would create a cycle, until all vertices are connected.

*Example:* For a graph with 5 vertices, Kruskal's will select 4 edges for the MST with no cycles.

> **tip**
>
> Edexcel requires you to list edges in the order you selected them, and explicitly state where you skipped an edge to avoid a cycle to get full method marks.

**Worked example:** Find the MST and its total weight for the following graph: Vertices A, B, C, D. Edges: AB=3, AC=5, BC=1, BD=4, CD=2.

1. Step 1: Sort all edges by weight ascending: BC (1), CD (2), AB (3), BD (4), AC (5)
2. Step 2: Add BC (weight 1): vertices B and C are connected, no cycle formed
3. Step 3: Add CD (weight 2): vertices B, C, D are connected, no cycle formed
4. Step 4: Add AB (weight 3): all 4 vertices are connected, stop
5. Step 5: Total MST weight = 1 + 2 + 3 = 6, selected edges: BC, CD, AB

*Calculator:* allowed

## Prim's Algorithm for Minimum Spanning Trees

**Prim's Algorithm** — Greedy algorithm that builds an MST starting from any chosen vertex, adding the smallest weight edge that connects a vertex in the existing tree to a vertex outside the tree, until all vertices are included. Can be applied directly to a network diagram or an adjacency matrix.

*Example:* For a 4-vertex graph, Prim's will add 3 edges to form a valid MST, with no cycles.

> **info**
>
> For the matrix version of Prim's, cross out the row of each vertex as you add it to the tree, then select the smallest value in the remaining columns at each step.

**Worked example:** Use the matrix version of Prim's starting at vertex A to find the MST for the adjacency matrix below: Rows/columns A,B,C,D. A: -,3,5,-; B:3,-,1,4; C:5,1,-,2; D:-,4,2,-.

1. Step 1: Start at A, cross out row A. The smallest value in uncrossed rows for columns not added is 3 (edge AB). Add AB, weight 3
2. Step 2: Cross out row B. The smallest value in uncrossed rows for columns not added is 1 (edge BC). Add BC, weight 1
3. Step 3: Cross out row C. The smallest value in uncrossed rows for columns not added is 2 (edge CD). Add CD, weight 2
4. Step 4: All 4 vertices are added, total MST weight = 3 + 1 + 2 = 6, matching the Kruskal's result

*Calculator:* allowed

## Converting Between Networks and Adjacency Matrices

Edexcel often asks you to convert a graph diagram to an adjacency matrix, or interpret a matrix to draw a network, before applying Prim's algorithm. For undirected graphs, the matrix is symmetric, with dashes or ∞ on the diagonal (no edges from a vertex to itself) and dashes or ∞ where no edge exists between two vertices.

**Worked example:** Convert the 4-vertex network from the earlier Kruskal's example to an adjacency matrix.

1. Step 1: Label rows and columns A, B, C, D in the same order
2. Step 2: Fill diagonal entries with "-" as there are no self-edges
3. Step 3: Enter edge weights for each pair: AB=3, AC=5, BC=1, BD=4, CD=2
4. Step 4: Fill remaining entries (AD) with "-" as no edge exists between A and D. The resulting matrix matches the one used in the Prim's matrix example.

*Calculator:* allowed

## Dijkstra's Algorithm for Shortest Path

**Dijkstra's Algorithm** — Greedy algorithm that finds the shortest path from a single start vertex to all other vertices in a graph with non-negative edge weights. Uses temporary labels for tentative distances, which are updated to permanent labels once the shortest distance to that vertex is confirmed.

*Example:* Dijkstra's can be used to find the shortest route between two towns on a map where edges represent roads and weights represent travel time.

> **tip**
>
> Edexcel requires you to show all temporary labels, cross out old labels when updated, and clearly mark permanent labels (often by circling or underlining them). You must also state the final path and its total weight to get full marks.

**Worked example:** Find the shortest path from A to D using Dijkstra's algorithm on the graph: A connected to B (3), A connected to C (5); B connected to C (1), B connected to D (4); C connected to D (2).

1. Step 1: Label A with permanent distance 0. Temporary labels: B=3, C=5, D=∞
2. Step 2: Select the smallest temporary label (B=3), mark as permanent. Update adjacent vertices: C = min(5, 3+1=4) → 4; D = min(∞, 3+4=7) →7
3. Step 3: Select the smallest temporary label (C=4), mark as permanent. Update adjacent vertex D = min(7, 4+2=6) →6
4. Step 4: Select the smallest temporary label (D=6), mark as permanent. All vertices processed. Shortest path: A→B→C→D, total weight 6.

*Calculator:* allowed

## Common pitfalls

- **Wrong:** Adding edges that create cycles in Kruskal's algorithm
  - Why it fails: Edges are sorted by weight, but you must check if the two vertices of the edge are already connected. Adding a cycle edge increases total weight unnecessarily and gives an invalid MST.
  - Correct: After sorting edges, check if the two endpoints of each edge are in separate connected components before adding it. Explicitly note skipped edges in your working for the examiner.
- **Wrong:** Forgetting to cross out rows when using matrix Prim's algorithm
  - Why it fails: If you do not cross out rows of vertices already added to the tree, you may accidentally select an edge connecting two vertices already in the tree, creating a cycle.
  - Correct: Every time you add a vertex to your MST, immediately cross out its row in the adjacency matrix before selecting the next smallest edge.
- **Wrong:** Stopping Dijkstra's algorithm as soon as you label the end vertex, before confirming it is permanent
  - Why it fails: A temporary label may be updated to a smaller value later if a shorter path is found via another vertex.
  - Correct: Only stop Dijkstra's when the target vertex has a permanent label, or all vertices are processed.
- **Wrong:** Using negative edge weights with Dijkstra's algorithm
  - Why it fails: Dijkstra's is not designed for negative weights, and will return incorrect shortest path results if negative edges are present.
  - Correct: Confirm all edge weights are non-negative before applying Dijkstra's, as required for all Edexcel D1 exam questions.
- **Wrong:** Failing to list the order of edge/vertex selection in your answer
  - Why it fails: Edexcel awards method marks for correct ordering, even if you make a small arithmetic error later. Skipping this step loses easy marks.
  - Correct: Always write the ordered list of edges (for Kruskal/Prim) or permanent labels (for Dijkstra) clearly, in the order you selected them.

## Cheatsheet

| Algorithm | Use Case | Key Steps | Exam Requirement |
| --- | --- | --- | --- |
| Kruskal's | Find MST | 1. Sort edges by weight ascending; 2. Add edges skipping cycles; 3. Stop when all vertices connected | List edges in selection order, note skipped cycle edges |
| Prim's (Network) | Find MST | 1. Pick start vertex; 2. Add smallest adjacent edge to tree; 3. Repeat until all vertices connected | Show order of vertex/edge addition |
| Prim's (Matrix) | Find MST from adjacency matrix | 1. Pick start vertex, cross out its row; 2. Select smallest value in remaining columns; 3. Cross out row of new vertex, repeat | Show crossed out rows for each step |
| Dijkstra's | Find shortest path between two vertices | 1. Label start vertex with permanent 0; 2. Update temporary labels for adjacent vertices; 3. Make smallest temporary label permanent, repeat until target is permanent | Show all temporary/permanent labels, state final path and weight |

## What's next

Now that you have mastered core graph algorithms for Edexcel IAL D1, you are ready to move to more advanced decision mathematics topics. Next, you will learn route inspection and travelling salesman problems, which build on the graph logic you have practiced here. You should also practice past paper questions on these algorithms to refine your speed and accuracy, as they appear in almost every D1 exam paper, accounting for 15-25% of total marks per paper. Make sure you follow Edexcel's required working format to avoid losing method marks.

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/edexcel-ial-math-d1-algorithms-on-graphs/