How to Solve: IB AI HL – Graph Theory (Minimum Spanning Tree, Dijkstra, Traveling Salesman)

How to Solve: IB AI HL – Graph Theory (Minimum Spanning Tree, Dijkstra, Traveling Salesman)

Introduction

"Mastering Minimum Spanning Trees, Dijkstra’s algorithm, and the Traveling Salesman Problem could earn you 10+ marks on your IB AI HL exam—and help you design the cheapest network for a city, find the fastest route for a delivery driver, or even plan a space mission. Let’s break it down so you can solve these problems fast and accurately under exam pressure."

What You Need To Know First

Before diving in, make sure you understand:
1. Graph basics – Vertices (nodes), edges, weights, directed vs. undirected graphs.
2. Adjacency matrices – How to read and interpret them.
3. Basic algorithms – How to follow step-by-step rules (like Prim’s or Kruskal’s).

If you’re shaky on any of these, pause and review them first—this guide assumes you’re solid on the basics.

Key Vocabulary

Formulas To Know

1. Prim’s Algorithm (for MST)

• What it does: Builds an MST by always adding the cheapest edge connected to the current tree.
• No formula to memorize – Just follow the steps (given below).
• MEMORISE THIS: Always pick the smallest available edge that doesn’t create a cycle.

2. Kruskal’s Algorithm (for MST)

• What it does: Builds an MST by sorting all edges and adding the smallest ones that don’t create cycles.
• No formula to memorize – Just sort edges and check for cycles.
• MEMORISE THIS: Use Union-Find (Disjoint Set) to detect cycles efficiently.

3. Dijkstra’s Algorithm (for Shortest Path)

• Formula (conceptual):
• distance[vertex] = min(distance[vertex], distance[current] + weight(current → vertex))
• What it means:
• For each vertex, update its shortest known distance from the start.
• MEMORISE THIS: Always pick the unvisited vertex with the smallest current distance next.

4. Traveling Salesman Problem (TSP) – Nearest Neighbor Heuristic

• What it does: Approximates the shortest route by always going to the nearest unvisited city.
• No formula to memorize – Just follow the steps (given below).
• MEMORISE THIS: This is a heuristic (not always optimal), but it’s fast for exams.

Step-by-Step Method

A. Minimum Spanning Tree (MST) – Prim’s Algorithm

When to use: When you need the cheapest way to connect all vertices without cycles.

Steps:
1. Pick any starting vertex. Mark it as "visited."
2. List all edges connected to visited vertices. Include their weights.
3. Pick the smallest edge that connects a visited vertex to an unvisited one.
4. Add the new vertex to the MST. Mark it as visited.
5. Repeat steps 2-4 until all vertices are visited.
6. Sum the weights of the edges in the MST for the total cost.

Example (Prim’s): Graph:

A --5-- B --3-- C
|       |       |
7       2       4
|       |       |
D --6-- E --1-- F

Step-by-step:
1. Start at A (visited: {A}).
2. Edges from A: A-B (5), A-D (7). Smallest: A-B (5).
3. Add B (visited: {A, B}). Edges: A-D (7), B-C (3), B-E (2). Smallest: B-E (2).
4. Add E (visited: {A, B, E}). Edges: A-D (7), B-C (3), E-D (6), E-F (1). Smallest: E-F (1).
5. Add F (visited: {A, B, E, F}). Edges: A-D (7), B-C (3), E-D (6), F-C (4). Smallest: F-C (4).
6. Add C (visited: {A, B, E, F, C}). Edges: A-D (7), C-B (3, already visited), E-D (6). Smallest: E-D (6).
7. Add D (visited: all). MST complete. MST edges: A-B (5), B-E (2), E-F (1), F-C (4), E-D (6). Total cost: 5 + 2 + 1 + 4 + 6 = 18.

B. Minimum Spanning Tree (MST) – Kruskal’s Algorithm

When to use: When edges are already sorted or you prefer a "sort-and-select" approach.

Steps:
1. Sort all edges from smallest to largest weight.
2. Pick the smallest edge. If it doesn’t create a cycle, add it to the MST.
3. Repeat step 2 until all vertices are connected (MST has n-1 edges for n vertices).
4. Sum the weights of the edges in the MST.

Example (Kruskal’s): Same graph as above:

Edges sorted by weight:
E-F (1), B-E (2), B-C (3), F-C (4), A-B (5), E-D (6), A-D (7)

Step-by-step:
1. Add E-F (1). No cycle.
2. Add B-E (2). No cycle.
3. Add B-C (3). No cycle.
4. Add F-C (4). Cycle! (B-C-F-E-B) → Skip.
5. Add A-B (5). No cycle.
6. Add E-D (6). No cycle. Now all vertices connected (6 vertices → 5 edges). MST edges: E-F (1), B-E (2), B-C (3), A-B (5), E-D (6). Total cost: 1 + 2 + 3 + 5 + 6 = 17 (Note: This is a different MST than Prim’s, but same cost!).

C. Dijkstra’s Algorithm (Shortest Path)

When to use: When you need the shortest path from one vertex to all others.

Steps:
1. Set distance to start vertex = 0. All others = ∞.
2. Pick the unvisited vertex with the smallest distance. Mark it as current.
3. For each neighbor of current: - Calculate distance[current] + weight(current → neighbor). - If this is smaller than the neighbor’s current distance, update it.
4. Mark current as visited. It’s now finalized.
5. Repeat steps 2-4 until all vertices are visited.
6. Read off the shortest paths from the distance table.

Example (Dijkstra’s): Graph:

      A
    4/ \2
   B---C
  3|   |1
   D---E
     5

Start at A. Find shortest paths to all others.

Step-by-step:
1. Distances: A=0, B=∞, C=∞, D=∞, E=∞. Visited: {}.
2. Pick A (smallest unvisited). Update neighbors: - A→B: 0 + 4 = 4 < ∞ → B=4 - A→C: 0 + 2 = 2 < ∞ → C=2 Visited: {A}.
3. Pick C (smallest unvisited: C=2). Update neighbors: - C→B: 2 + 1 = 3 < 4 → B=3 - C→E: 2 + 1 = 3 < ∞ → E=3 Visited: {A, C}.
4. Pick B (smallest unvisited: B=3). Update neighbors: - B→D: 3 + 3 = 6 < ∞ → D=6 Visited: {A, C, B}.
5. Pick E (smallest unvisited: E=3). Update neighbors: - E→D: 3 + 5 = 8 > 6 → No update. Visited: {A, C, B, E}.
6. Pick D (only unvisited). No updates. Visited: all. Shortest paths: - A→B: 3 (A→C→B) - A→C: 2 (A→C) - A→D: 6 (A→C→B→D) - A→E: 3 (A→C→E)

D. Traveling Salesman Problem (TSP) – Nearest Neighbor Heuristic

When to use: When you need a quick (but not always optimal) route visiting all vertices once and returning to start.

Steps:
1. Pick a starting vertex.
2. Go to the nearest unvisited vertex. Mark it as visited.
3. Repeat step 2 until all vertices are visited.
4. Return to the start.
5. Sum the weights of the edges in the route.

Example (TSP): Graph (complete, undirected):

      A
    3/ \2
   B---C
  4|   |1
   D---E
     5

Start at A.

Step-by-step:
1. From A, nearest is C (2). Route: A→C.
2. From C, nearest unvisited is E (1). Route: A→C→E.
3. From E, nearest unvisited is D (5). Route: A→C→E→D.
4. From D, nearest unvisited is B (4). Route: A→C→E→D→B.
5. Return to A from B (3). Route: A→C→E→D→B→A. Total cost: 2 (A→C) + 1 (C→E) + 5 (E→D) + 4 (D→B) + 3 (B→A) = 15.

(Note: This may not be the absolute shortest route, but it’s a fast approximation for exams.)

Worked Examples

Example 1 – Basic (Prim’s Algorithm)

Graph:

      A
    2/ \3
   B---C
  1|   |4
   D---E
     5

Question: Find the MST using Prim’s. Start at A.

Solution:
1. Start at A (visited: {A}).
2. Edges from A: A-B (2), A-C (3). Smallest: A-B (2).
3. Add B (visited: {A, B}). Edges: A-C (3), B-D (1). Smallest: B-D (1).
4. Add D (visited: {A, B, D}). Edges: A-C (3), D-E (5). Smallest: A-C (3).
5. Add C (visited: {A, B, D, C}). Edges: C-E (4), D-E (5). Smallest: C-E (4).
6. Add E (visited: all). MST edges: A-B (2), B-D (1), A-C (3), C-E (4). Total cost: 2 + 1 + 3 + 4 = 10.

What we did and why: - We always picked the smallest available edge connected to the growing tree. - This ensures the total cost is minimized without creating cycles.

Example 2 – Medium (Dijkstra’s Algorithm)

Graph (directed):

      A
    4↘ ↙2
   B ← C
  3↓   ↓1
   D → E
     5

Question: Find the shortest path from A to all other vertices.

Solution:
1. Distances: A=0, B=∞, C=∞, D=∞, E=∞. Visited: {}.
2. Pick A (smallest unvisited). Update neighbors: - A→B: 0 + 4 = 4 → B=4 - A→C: 0 + 2 = 2 → C=2 Visited: {A}.
3. Pick C (smallest unvisited: C=2). Update neighbors: - C→B: 2 + 1 = 3 < 4 → B=3 - C→E: 2 + 1 = 3 → E=3 Visited: {A, C}.
4. Pick B (smallest unvisited: B=3). Update neighbors: - B→D: 3 + 3 = 6 → D=6 Visited: {A, C, B}.
5. Pick E (smallest unvisited: E=3). Update neighbors: - E→D: 3 + 5 = 8 > 6 → No update. Visited: {A, C, B, E}.
6. Pick D (only unvisited). No updates. Shortest paths: - A→B: 3 (A→C→B) - A→C: 2 (A→C) - A→D: 6 (A→C→B→D) - A→E: 3 (A→C→E)

What we did and why: - We updated distances whenever we found a shorter path. - Always picking the smallest unvisited vertex ensures we don’t miss the shortest path.

Example 3 – Exam-Style (TSP + Adjacency Matrix)

Adjacency matrix:

    A  B  C  D
A [ 0  3  4  2 ]
B [ 3  0  1  5 ]
C [ 4  1  0  6 ]
D [ 2  5  6  0 ]

Question: Use the Nearest Neighbor heuristic to find a route starting and ending at A. Calculate the total cost.

Solution:
1. Start at A.
2. From A, nearest is D (2). Route: A→D.
3. From D, nearest unvisited is B (5). Route: A→D→B.
4. From B, nearest unvisited is C (1). Route: A→D→B→C.
5. Return to A from C (4). Route: A→D→B→C→A. Total cost: 2 (A→D) + 5 (D→B) + 1 (B→C) + 4 (C→A) = 12.

What we did and why: - We followed the heuristic to quickly approximate a route. - The adjacency matrix told us edge weights without needing a diagram.

Common Mistakes

Exam Traps

1-Minute Recap

"Here’s what you need to remember the night before your exam:
1. Minimum Spanning Tree (MST): - Use Prim’s (start anywhere, grow the tree) or Kruskal’s (sort edges, avoid cycles). - Always pick the smallest edge that doesn’t create a cycle.
2. Dijkstra’s Algorithm: - Start at your chosen vertex, set its distance to 0. - Update neighbors’ distances, then pick the smallest unvisited vertex next. - Repeat until all vertices are visited.
3. Traveling Salesman Problem (TSP): - Use the Nearest Neighbor heuristic for a quick answer. - Start at a vertex, go to the nearest unvisited one, repeat, then return to start.
4. Common traps: - Check if the graph is directed (arrows matter!). - Don’t forget to return to start in TSP. - Always update distances in Dijkstra’s—missing this costs marks!

You’ve got this. Now go ace that exam!