What are the key differences between Prim's and Kruskal's algorithms in graph theory?

Prim's and Kruskal's algorithms are both used to find the minimum spanning tree of a graph, which is a subset of edges that connects all vertices with the minimum possible total edge weight. Prim's algorithm starts with a single vertex and grows the spanning tree by adding the cheapest edge from the tree to a vertex not yet in the tree. In contrast, Kruskal's algorithm sorts all edges by weight and adds them one by one to the spanning tree, provided they don't form a cycle. Prim's is more efficient for dense graphs, while Kruskal's is better for sparse graphs.

How does Dijkstra's algorithm work for finding the shortest path in a graph?

Dijkstra's algorithm is used to find the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative weights. It works by initializing the distance to the starting vertex as zero and all other vertices as infinity. The algorithm then repeatedly selects the vertex with the smallest known distance, updates the distances to its neighbors, and marks it as visited. This process continues until all vertices have been visited, resulting in the shortest path from the start vertex to each vertex in the graph.

What is the significance of the Bellman-Ford algorithm in graph theory?

The Bellman-Ford algorithm is significant because it can handle graphs with negative edge weights, unlike Dijkstra's algorithm. It is used to find the shortest path from a single source vertex to all other vertices in a graph. The algorithm iteratively relaxes all edges, updating the shortest path estimates, and can detect negative weight cycles. If a negative cycle is reachable from the source, the algorithm indicates that no solution exists. This makes Bellman-Ford particularly useful in networks where negative weights might occur.

How do you determine if a graph is connected using graph algorithms?

To determine if a graph is connected, you can use Depth-First Search (DFS) or Breadth-First Search (BFS). Starting from any vertex, perform a DFS or BFS to explore all reachable vertices. If all vertices are visited during this traversal, the graph is connected. For undirected graphs, this means there is a path between every pair of vertices. For directed graphs, you can check strong connectivity by ensuring every vertex is reachable from every other vertex, often using Kosaraju's or Tarjan's algorithm.

What role do adjacency matrices and lists play in graph algorithms?

Adjacency matrices and lists are two common ways to represent graphs in algorithms. An adjacency matrix is a 2D array where each cell (i, j) indicates the presence and weight of an edge between vertices i and j. It is efficient for dense graphs but requires more space. An adjacency list, on the other hand, is an array of lists where each list contains the neighbors of a vertex. It is more space-efficient for sparse graphs and allows faster iteration over neighbors. The choice between them depends on the graph's density and the operations needed.

Why is "Erasing replaced working labels instead of striking them through" a common mistake in Algorithms on graphs II?

Why it happens: Keeping the page tidy. How to avoid it: Edexcel mark schemes inspect EVERY working label. Strike replaced labels through; write the new label beside (or below). Never use rubber/eraser. Source: WDM01/01 Examiner Reports — flagged every session

Why is "Assigning permanent labels in the wrong order" a common mistake in Algorithms on graphs II?

Why it happens: Confusing 'next vertex' with 'most recent neighbour'. How to avoid it: Always pick the UNVISITED vertex with the SMALLEST working label as the next to assign a permanent label. Compare ALL working labels each step, not just neighbours of the most recent vertex.

Why is "Trying to apply route inspection without listing the degrees" a common mistake in Algorithms on graphs II?

Why it happens: Jumping to the algorithm. How to avoid it: STEP 1 of route inspection is ALWAYS: list every vertex's degree and identify which are odd. The algorithm depends on the number of odd vertices (0, 2, or 4).

Why is "Forgetting to return to the starting vertex in nearest-neighbour TSP" a common mistake in Algorithms on graphs II?

Why it happens: Algorithm 'ends' after the last vertex. How to avoid it: A TSP TOUR is CLOSED — it must return to start. Always add the final return-edge weight.

Why is "Adding the two shortest edges from $v$ to the MST of the WHOLE graph (not the graph minus $v$)" a common mistake in Algorithms on graphs II?

Why it happens: Forgetting to delete the chosen vertex. How to avoid it: DELETE the chosen vertex FIRST, then compute the MST of what remains, then add the two shortest edges incident with the DELETED vertex.

Why is "Picking the two shortest edges in the entire graph instead of the two shortest from $v$" a common mistake in Algorithms on graphs II?

Why it happens: Misreading the procedure. How to avoid it: Only edges INCIDENT WITH v count for the +2 part. The MST and the 2 edges are joined at v to make a closed structure.

Decision Mathematics 1Edexcel International A Levels Mathematics (XMA01-YMA01)

Algorithms on graphs II

Work through the notes, try the practice questions, then take the quiz. The report tells you exactly what to revise next.

Previous Next

Learn this Topic

Start with the slides for the quick version, then go deeper with the full study notes.

Detailed Notes

Full prose, callouts and a recap — built for A* mastery, not just a quick scan.

Take these study notes with you

Download a branded PDF — full prose, callouts, recap and memorise list for Algorithms on graphs II, ready to print or save offline.

Algorithms on Graphs II Study Notes — Edexcel IAL Mathematics D1 (WDM01/01, 2018 spec — 2026 onwards)

DIJKSTRA finds shortest paths from a source to every other vertex (non-negative weights only). ROUTE INSPECTION (Chinese postman) finds the cheapest closed walk that covers every edge — handles 0, 2, or 2k odd vertices by repeating the shortest paths between them. TSP finds the cheapest closed walk visiting every vertex once. Upper bound: NEAREST-NEIGHBOUR heuristic from a starting vertex. Lower bound: MST(graph minus a vertex) $+$ two shortest edges from that vertex.

What you’ll learn

Mapped to the Pearson Edexcel International A Levels XMA01-YMA01 syllabus (2026 onwards).

D1 3.1 — Apply Dijkstra's algorithm to find shortest paths in a weighted graph.
D1 3.2 — Apply route inspection (Chinese postman) for $0, 2,$ or $\ge 4$ odd-degree vertices.
D1 3.3 — Find upper and lower bounds for the Travelling Salesman Problem using nearest-neighbour and the MST method.

Dijkstra's algorithm

Shortest path from a source vertex to every other vertex.

Setup. A weighted graph with NON-NEGATIVE edge weights. Find the shortest distance from a chosen source $s$ to every other vertex.

Edexcel labelling convention. Each vertex has THREE boxes:

Order of permanent assignment (1, 2, 3, ...).
Permanent label (final shortest distance from $s$ ).
Working labels (tentative distances, written below, with replaced ones struck through).

Procedure.

Assign permanent label $0$ to the source $s$ ; order $1$ .
Update working labels at each NEIGHBOUR of $s$ : label of $s$ + edge weight.
Find the UNVISITED vertex with the SMALLEST current working label; assign it a permanent label equal to its working label; record the order.
Update working labels at the neighbours of the newly permanent vertex: new label = $\min(\text{current working}, \text{label of new permanent} + \text{edge weight})$ . Strike through replaced labels.
Repeat 3-4 until every vertex has a permanent label.

Reading off the path. Once Dijkstra terminates, the permanent label at the destination $t$ is the shortest distance. To recover the path, work BACKWARDS from $t$ : at each vertex $v$ in the path, the predecessor $u$ satisfies $\text{permanent}(v) - w(u, v) = \text{permanent}(u).$

Worked example (recap from topical).

Network: $AB=5, AC=2, BC=4, BD=8, BE=10, CD=6, CE=9, DE=3$ . Source $A$ .

Vertex	Order	Permanent	Working (left → right)
$A$	1	0	—
$B$	3	5	$5$
$C$	2	2	$2$
$D$	4	8	$8$
$E$	5	11	$\sout{11}, 11$

Trace path from $E$ : $11 - 9 = 2 = \text{label}(C)$ so $C \to E$ ; or $11 - 3 = 8 = \text{label}(D)$ so $D \to E$ . Both shortest. From $C$ : $2 - 2 = 0 = \text{label}(A)$ so $A \to C$ direct. Path $A \to C \to E$ (or $A \to C \to D \to E$ ).

Why non-negative weights matter. Dijkstra assumes a permanent label is final. If negative weights are allowed, a longer-looking detour could become shorter through a negative edge — Dijkstra fails. (For graphs with negative weights, use Bellman-Ford — NOT on the D1 syllabus.)

Dijkstra labels each vertex with the shortest distance from the source; trace back along edges that satisfy perm(v) − w = perm(u).

Source has permanent label $0$ .
Smallest unvisited working label gets the next permanent label.
Update neighbours by min(current, new).
Strike through replaced labels — never erase.
Trace path backwards using $\text{perm}(v) - w(u,v) = \text{perm}(u)$ .

Route inspection (Chinese postman)

Closed walk traversing every edge. Handle odd vertices by pairing.

Problem. A traveller must traverse every edge of a weighted graph at least once, starting and finishing at the same vertex. Find the minimum total weight.

Theorem (Euler). A connected graph has a closed walk traversing every edge EXACTLY ONCE (an EULERIAN CIRCUIT) if and only if every vertex has even degree.

Algorithm.

Compute the degree of every vertex.
List the ODD-degree vertices. There are always an EVEN number of them (handshaking lemma).
Case $0$ odd: the answer is the total edge weight; an Eulerian circuit exists.
Case $2$ odd: find the shortest path between the two odd vertices; ADD its weight to the total edge weight. Those edges are traversed twice; all others once.
Case $2k$ odd ( $k \ge 2$ ): pair up the odd vertices in all possible ways (there are $(2k-1)!! = (2k-1)(2k-3)\cdots 1$ pairings); for each pairing, sum the shortest-path distances between pairs; pick the MINIMUM-SUM pairing; ADD that sum to the total edge weight.

Worked example (2 odd).

Edges (km): $AB=4, AC=5, BC=3, BD=6, CD=7, CE=4, DE=5$ . Total $= 34$ .

Degrees: $A=2, B=3, C=4, D=3, E=2$ . Odd: $B, D$ .

Shortest $B$ - $D$ path: direct $BD = 6$ .

Answer: $34 + 6 = 40$ .

Worked example (4 odd).

Suppose total edge weight $= 50$ and the 4 odd vertices are $P, Q, R, S$ with shortest-path distances $PQ = 5, PR = 7, PS = 8, QR = 6, QS = 9, RS = 4$ .

Three pairings:

$(PQ)(RS)$ : $5 + 4 = 9$ .
$(PR)(QS)$ : $7 + 9 = 16$ .
$(PS)(QR)$ : $8 + 6 = 14$ .

Minimum $= 9$ . Answer: $50 + 9 = 59$ .

Why it works. A closed walk uses each edge an even number of times PER VERTEX. Edges traversed once contribute $1$ to that vertex's tally; to make every vertex EVEN, the odd vertices must each gain one more incidence — achieved by repeating a path that connects them in pairs.

Number of pairings.

# odd vertices	# pairings
2	1
4	3
6	15
8	105

Beyond 6, hand evaluation becomes unwieldy — exam questions cap at 4.

0 odd: answer = total edge weight.
2 odd: add shortest path between them.
4 odd: try all $3$ pairings, pick the minimum.
Edges along chosen pairings are traversed TWICE.

Travelling Salesman Problem

Cheapest closed tour visiting every vertex once. Upper bound + lower bound.

Problem. Find a closed walk that visits every vertex EXACTLY ONCE and returns to the start, with minimum total weight. Edexcel D1 uses the COMPLETE WEIGHTED GRAPH version (an edge between every pair) and assumes the TRIANGLE INEQUALITY holds.

Why bounds, not exact? TSP is NP-hard — no known polynomial-time algorithm. D1 finds bounds:

UPPER BOUND via the nearest-neighbour algorithm — a valid tour, so an actual upper bound on the optimum.
LOWER BOUND via MST + 2 shortest edges from a deleted vertex.

Nearest-neighbour algorithm (UPPER BOUND).

Pick a starting vertex.
From the current vertex, go to the NEAREST UNVISITED vertex.
Repeat until all vertices are visited.
Return to the starting vertex.

The resulting tour length is an UPPER BOUND. Different starting vertices give different upper bounds — usually $5$ starting points $\Rightarrow$ $5$ upper bounds; the LOWEST is best.

Worked example (UB). Distance matrix:

	A	B	C	D	E
A	—	12	15	9	11
B	12	—	8	14	7
C	15	8	—	10	6
D	9	14	10	—	13
E	11	7	6	13	—

Start at $A$ : nearest = $D$ ( $9$ ); from $D$ nearest unvisited = $C$ ( $10$ ); from $C$ = $E$ ( $6$ ); from $E$ = $B$ ( $7$ ); return $B \to A$ ( $12$ ). Tour: $A \to D \to C \to E \to B \to A$ , length $9+10+6+7+12 = 44$ .

Lower-bound algorithm.

DELETE one vertex $v$ .
Compute the MST of the remaining graph.
Add the TWO SHORTEST EDGES incident with $v$ .

The result is a LOWER BOUND on the optimal TSP tour.

Worked example (LB). Delete $A$ . Remaining edges: $BC=8, BD=14, BE=7, CD=10, CE=6, DE=13$ .

MST (Kruskal): $CE=6, BE=7, CD=10$ (the edge $BC=8$ forms a cycle with $BE, CE$ — reject). Total MST $= 23$ .

Two shortest edges from $A$ : $AD = 9, AE = 11$ . Sum $= 20$ .

Lower bound $= 23 + 20 = 43$ .

Bounding the optimal tour. $43 \le \text{optimal} \le 44$ . The true optimal is $43$ or $44$ .

Choosing $v$ for the best LB. Different vertices give different lower bounds. To MAXIMISE the lower bound (i.e. make it as tight as possible), the rule of thumb is: delete the vertex whose two smallest incident edges are LARGEST. Exam questions typically tell you which vertex to delete; if not, try the obvious candidate.

Practical exam advice.

Always state $\text{LB} \le \text{optimal} \le \text{UB}$ at the end.
If UB = LB, the optimal tour IS that value.
Mention what triangle inequality assumes (direct edge is at most as long as any detour).

Nearest-neighbour → upper bound (a valid tour).
MST(minus $v$ ) + 2 shortest from $v$ → lower bound.
Different starting vertices for NN → different UBs.
Different $v$ for deletion → different LBs.
Always state $\text{LB} \le \text{optimal} \le \text{UB}$ .

Quick reference table

What each algorithm does and when to use it.

Algorithm	Input	Output	Edexcel notation
Dijkstra	Source vertex + weighted graph (non-negative weights)	Shortest distance from source to every other vertex	Order, permanent label, working labels (struck through)
Route inspection	Connected weighted graph + start/finish vertex (closed walk)	Min total weight to traverse every edge	List degrees; pair odd vertices; add shortest paths
TSP nearest-neighbour	Complete weighted graph + start vertex	Upper bound for optimal tour	Trace tour; state length
TSP MST lower bound	Complete weighted graph + chosen vertex to delete	Lower bound for optimal tour	MST + two shortest edges; state $\text{LB} \le \text{opt}$

Choosing the right algorithm.

'Shortest path from $X$ to $Y$ ' → Dijkstra.
'Postman must cover every road' → Route inspection.
'Salesman must visit every city once and return' → TSP.

Common pitfalls (see Common Mistakes section).

Erasing Dijkstra labels.
Skipping degree analysis in route inspection.
Forgetting to return to start in nearest-neighbour.
Using MST of the WHOLE graph instead of $G \setminus \{v\}$ for TSP LB.

Shortest path → Dijkstra.
Cover every edge → Route inspection.
Visit every vertex → TSP.
TSP gives bounds, not exact answer (D1 level).

How it’s examined

This subtopic is a $14$ - $18$ -mark question on every WDM01/01 paper — often the highest-value question. Standard format: (a) Dijkstra from a given source ( $7$ - $9$ marks) — every working label and final route required; (b) route inspection ( $5$ - $7$ marks) — list degrees, identify odd vertices, compute pairings if $\ge 4$ odd; (c) TSP nearest-neighbour upper bound ( $3$ - $4$ marks); (d) TSP lower bound by deletion ( $4$ - $6$ marks); (e) state the inequality $\text{LB} \le \text{optimal} \le \text{UB}$ . Marks lost: erasing Dijkstra labels, skipping degree analysis, forgetting the return-to-start in NN, computing MST of the wrong subgraph. The mark scheme heavily rewards methodical, tabulated working.

Sources: Pearson Edexcel International Advanced Level Mathematics specification (2018 — current for 2026 onwards); Edexcel IAL Mathematical Formulae and Statistical Tables (2018); WDM01/01 Examiner Reports — January 2023, June 2023, January 2024, June 2024. Last reviewed 2026-05-12.

Master this Topic

Worked examples, formulae, definitions and the mistakes examiners flag — everything you need to push from a pass to an A*.

Take this whole topic with you

Download a branded revision sheet — worked examples, formulae, definitions and common mistakes for Algorithms on graphs II, ready to print or save as PDF.

Step-by-step worked examples — Algorithms on graphs II

Step-by-step solutions to past-paper-style questions on algorithms on graphs ii, written exactly the way a tutor would explain them at the board.

1Dijkstra's shortest path (8 marks, D1)
Extended• Adapted from WDM01/01 June 2024 Q6• Dijkstra, shortest path
Question
A network has vertices $A, B, C, D, E$ and edges $AB=5, AC=2, BC=4, BD=8, BE=10, CD=6, CE=9, DE=3$ . Use Dijkstra's algorithm to find the shortest path from $A$ to $E$ and state its length.
Step-by-step solution
1. Step 1
  Setup. Each vertex holds (order, permanent label, working labels). Start at $A$ .
  
  Assign $A$ : order 1, permanent label $0$ .
  
  Update working labels at neighbours of $A$ : $B \leftarrow 5$ , $C \leftarrow 2$ .
2. Step 2
  Step 2. Smallest unvisited working label is $C$ ( $=2$ ). Assign $C$ : order 2, permanent label $2$ .
  
  Update from $C$ (distance $2$ ):
  
  $B$ : $2 + 4 = 6$ ; current working at $B$ is $5$ . Keep $5$ (smaller).
  
  $D$ : $2 + 6 = 8$ ; new label.
  
  $E$ : $2 + 9 = 11$ ; new label.
3. Step 3
  Step 3. Smallest unvisited working label is $B$ ( $=5$ ). Assign $B$ : order 3, permanent label $5$ .
  
  Update from $B$ (distance $5$ ):
  
  $D$ : $5 + 8 = 13$ ; current $8$ . Keep $8$ .
  
  $E$ : $5 + 10 = 15$ ; current $11$ . Keep $11$ .
4. Step 4
  Step 4. Smallest unvisited working label is $D$ ( $=8$ ). Assign $D$ : order 4, permanent label $8$ .
  
  Update from $D$ (distance $8$ ):
  
  $E$ : $8 + 3 = 11$ ; current $11$ . Tie — keep $11$ (no change in value, but mark that $D \to E$ is also a valid predecessor).
5. Step 5
  Step 5. Smallest unvisited working label is $E$ ( $=11$ ). Assign $E$ : order 5, permanent label $11$ . Algorithm terminates.
6. Step 6
  Trace the route back from $E$ . At $E$ (label $11$ ): which predecessor gives $11 - \text{edge}$ = predecessor's label?
  
  From $C$ : $11 - 9 = 2 =$ label of $C$ ✓ — route via $C$ .
  
  From $D$ : $11 - 3 = 8 =$ label of $D$ ✓ — route via $D$ .
  
  BOTH are valid shortest paths. Trace each:
  
  Path 1: $A \to C \to E$ , length $2 + 9 = 11$ .
  
  Path 2: $A \to C \to D \to E$ , length $2 + 6 + 3 = 11$ .
Answer
Shortest distance from $A$ to $E$ is $\mathbf{11}$ . Two equal-length shortest paths: $A \to C \to E$ (lengths $2, 9$ ) and $A \to C \to D \to E$ (lengths $2, 6, 3$ ).
Examiner tip
M1 set up Dijkstra (correct order at $A, C$ ). A1 each subsequent permanent label ( $\times 3$ ). A1 final permanent label at $E$ . B1 trace route back. A1 state path AND length. Edexcel mark schemes inspect EVERY working label at EVERY vertex — students who erase replaced labels lose marks. Show all working labels, struck through neatly.

2Route inspection: 2 odd vertices (6 marks, D1)

Extended• Adapted from WDM01/01 January 2024 Q5• route inspection, Chinese postman

Question

A road network has the following edge weights (km): $AB=4, AC=5, BC=3, BD=6, CD=7, CE=4, DE=5$ . A postman must traverse every road, starting and finishing at $A$ . Find the minimum total distance.

Step-by-step solution

Step 1
Total edge weight. $4 + 5 + 3 + 6 + 7 + 4 + 5 = 34$ km.

Step 2

Find odd-degree vertices.

Vertex	Adjacent edges	Degree
$A$	$AB, AC$	$2$ (even)
$B$	$AB, BC, BD$	$3$ (odd)
$C$	$AC, BC, CD, CE$	$4$ (even)
$D$	$BD, CD, DE$	$3$ (odd)
$E$	$CE, DE$	$2$ (even)

Two odd vertices: $B$ and $D$ .

Step 3
Shortest path from $B$ to $D$ . Possible routes:
- $B \to D$ direct: $6$ .
- $B \to C \to D$ : $3 + 7 = 10$ .
- $B \to A \to C \to D$ : $4 + 5 + 7 = 16$ .
- $B \to C \to E \to D$ : $3 + 4 + 5 = 12$ .
Shortest $= 6$ (direct edge $BD$ ).
Step 4
Repeat the shortest path between the odd vertices. Add $6$ to the total: $34 + 6 = 40$ km.
Step 5
Conclusion. Minimum closed walk = $40$ km, with edge $BD$ traversed twice (once normally, once 'repeated').

Answer

Total edges $= 34$ km. Odd vertices $B, D$ ; shortest $B$ - $D$ path $= 6$ (direct). Minimum route $= 34 + 6 = 40$ km. Route includes edge $BD$ twice.

Examiner tip

M1 list degrees AND identify the odd vertices. A1 odd vertices correct ( $B, D$ ). M1 find shortest path between them. A1 shortest $= 6$ . M1 add to total. A1 final answer $40$ km. The key insight: a closed walk traversing every edge can only handle EVEN degrees (you need to enter and leave each vertex equally); odd vertices force you to RETRAVERSE the cheapest connecting path.

3Route inspection: 4 odd vertices (8 marks, D1)
Challenge• Adapted from WDM01/01 June 2024 Q7• route inspection, pairings
Question
A graph has 4 odd-degree vertices $P, Q, R, S$ with these shortest-path distances between them: $PQ = 5, PR = 7, PS = 8, QR = 6, QS = 9, RS = 4$ . Total edge weight in the graph is $50$ . Find the optimal pairing of odd vertices and the minimum closed-walk length.
Step-by-step solution
1. Step 1
  Three pairings possible for 4 odd vertices:
  
  $(PQ)(RS)$ : $5 + 4 = 9$ .
  
  $(PR)(QS)$ : $7 + 9 = 16$ .
  
  $(PS)(QR)$ : $8 + 6 = 14$ .
2. Step 2
  Choose the minimum. Pairing 1: $(PQ)(RS)$ totals $9$ — the smallest.
3. Step 3
  Minimum closed-walk length. Add the chosen pairing total to the graph's total edge weight: $50 + 9 = 59$ .
4. Step 4
  Interpretation. The edges along the shortest $P$ - $Q$ path and the shortest $R$ - $S$ path are each TRAVERSED TWICE; every other edge is traversed exactly once.
Answer
Pairing $(PQ)(RS)$ minimises the extra distance ( $9$ ). Minimum route $= 50 + 9 = 59$ .
Examiner tip
B1 list all three pairings. A1 each pairing sum ( $\times 3$ ). B1 identify minimum. A1 add to total edge weight. A1 final answer. With $n$ odd vertices ( $n$ even), the number of pairings is $(n-1)!! = (n-1)(n-3)\cdots$ . For $n = 4$ , that's $3 \cdot 1 = 3$ . For $n = 6$ , that's $5 \cdot 3 \cdot 1 = 15$ . Beyond $n = 6$ , hand evaluation becomes impractical (real algorithm: minimum-weight matching).
4TSP upper bound by nearest neighbour (5 marks, D1)
Extended• Adapted from WDM01/01 January 2024 Q6(a)• TSP, nearest neighbour, upper bound
Question
A complete network with $5$ vertices has the following distance matrix (unit: km):

A B C D E
A — 12 15 9 11
B 12 — 8 14 7
C 15 8 — 10 6
D 9 14 10 — 13
E 11 7 6 13 —

Use the NEAREST-NEIGHBOUR algorithm starting at $A$ to find an upper bound for the Travelling Salesman tour.
Step-by-step solution
1. Step 1
  Start at $A$ . Visited $= \{A\}$ . Distances from $A$ : $B=12, C=15, D=9, E=11$ . Nearest = $D$ at $9$ .
  
  Go to $D$ . Tour so far: $A \to D$ (length $9$ ).
2. Step 2
  At $D$ . Visited $= \{A, D\}$ . Distances from $D$ to unvisited: $B=14, C=10, E=13$ . Nearest $= C$ at $10$ .
  
  Go to $C$ . Tour: $A \to D \to C$ (length $9 + 10 = 19$ ).
3. Step 3
  At $C$ . Visited $= \{A, D, C\}$ . Distances from $C$ to unvisited: $B=8, E=6$ . Nearest $= E$ at $6$ .
  
  Go to $E$ . Tour: $A \to D \to C \to E$ (length $19 + 6 = 25$ ).
4. Step 4
  At $E$ . Only $B$ left. $EB = 7$ .
  
  Go to $B$ . Tour: $A \to D \to C \to E \to B$ (length $25 + 7 = 32$ ).
5. Step 5
  Return to $A$ . $BA = 12$ .
  
  Final tour: $A \to D \to C \to E \to B \to A$ . Total $= 32 + 12 = 44$ .
  
  This is an UPPER BOUND for the optimal TSP tour.
Answer
Upper bound from nearest neighbour starting at $A$ : $A \to D \to C \to E \to B \to A$ with total $= 9 + 10 + 6 + 7 + 12 = 44$ km.
Examiner tip
M1 attempt nearest-neighbour from $A$ . A1 each correct next-vertex selection ( $\times 4$ ). A1 return to $A$ . B1 total = upper bound. Different starting vertices yield different upper bounds — Edexcel often asks 'try starting at $B$ — does this give a better upper bound?'. Always show the tour AND its length.
5TSP lower bound via MST (6 marks, D1)
Challenge• Adapted from WDM01/01 January 2024 Q6(b)• TSP, lower bound, MST
Question
Using the same matrix as the previous question, find a LOWER BOUND for the Travelling Salesman tour by deleting vertex $A$ , computing the MST of the remaining $4$ -vertex network, and adding the two shortest edges from $A$ .
Step-by-step solution
1. Step 1
  Delete $A$ . Remaining graph: $\{B, C, D, E\}$ with edges $BC=8, BD=14, BE=7, CD=10, CE=6, DE=13$ .
2. Step 2
  MST of $\{B, C, D, E\}$ (by Kruskal). Sort: $CE=6, BE=7, BC=8, CD=10, DE=13, BD=14$ .
  
  Accept $CE$ ( $6$ ).
  
  Accept $BE$ ( $7$ ).
  
  $BC = 8$ : cycle $B$ - $C$ - $E$ - $B$ — reject.
  
  Accept $CD$ ( $10$ ).
  
  $3 = n - 1$ edges accepted. MST weight $= 6 + 7 + 10 = 23$ .
3. Step 3
  Two shortest edges from $A$ . From the deleted vertex $A$ , edges are: $AB=12, AC=15, AD=9, AE=11$ .
  
  Two smallest: $AD=9$ and $AE=11$ . Sum $= 20$ .
4. Step 4
  Lower bound. $\text{MST} + 2\text{ shortest edges from } A = 23 + 20 = 43$ .
5. Step 5
  Comparison with upper bound. $43 \le \text{optimal} \le 44$ . The optimal tour is either $43$ or $44$ .
  
  The lower bound gives a tight RANGE for the true minimum tour.
Answer
MST of $\{B,C,D,E\}$ has weight $23$ (edges $CE, BE, CD$ ). Two shortest edges from $A$ : $AD = 9$ and $AE = 11$ , sum $20$ . Lower bound $= 23 + 20 = 43$ km. Combined with the upper bound $44$ , the optimal tour is between $43$ and $44$ .
Examiner tip
M1 delete $A$ and find MST of remaining graph. A1 MST weight ( $23$ ). M1 identify two shortest edges from $A$ . A1 sum ( $20$ ). M1 add. A1 lower bound $= 43$ . B1 state inequality $43 \le \text{optimal} \le 44$ . Edexcel mark schemes often ask 'which vertex's deletion gives the best lower bound?' — typically delete the vertex with the LARGEST 'second smallest edge' to maximise the bound.

Key Formulae — Algorithms on graphs II

The formulae you need to memorise for algorithms on graphs ii on the Pearson Edexcel IAL XMA01 / YMA01 paper, with every variable defined in plain English and a note on when to use it.

Dijkstra update rule
$\text{new label at } v \;=\; \min(\text{current label}, \;\text{label of } u + w(u, v))$
$u$
current vertex (just assigned a permanent label)
$v$
neighbour
$w(u, v)$
weight of edge $uv$
When to use
Each time a vertex receives a permanent label, update working labels at its neighbours. NOT in the IAL formula booklet.
Example
At $C$ with permanent label $2$ , neighbour $D$ with current label $\infty$ : new label $\min(\infty, 2 + 6) = 8$ .
Route inspection (Chinese postman) with 2 odd vertices
$\text{Min closed walk} \;=\; (\text{total edge weight}) + (\text{shortest path between the 2 odd vertices})$
$\text{odd}$
vertex of odd degree
When to use
Postman / road-sweeping problem where every edge must be traversed at least once, finishing where you started, and there are exactly two odd vertices. NOT in the IAL formula booklet.
Example
Total $= 34$ , odd vertices $B, D$ with shortest path $6$ ⇒ min walk $= 34 + 6 = 40$ .
TSP lower bound (delete-a-vertex method)
$\text{LB} \;=\; \text{MST}(G \setminus \{v\}) + (\text{two shortest edges incident with } v)$
$v$
any chosen vertex (often the one giving the largest LB)
$G \setminus \{v\}$
the graph with $v$ removed
When to use
Bounding the Travelling Salesman tour from below. NOT in the IAL formula booklet — Edexcel D1 procedure.
Example
Delete $A$ : MST weight $23$ + two shortest from $A$ ( $9 + 11 = 20$ ) ⇒ LB $= 43$ .

Key Definitions and Keywords — Algorithms on graphs II

Definitions to memorise and the exact keywords mark schemes credit for algorithms on graphs ii answers — sharpened from recent examiner reports for the 2026 Pearson Edexcel IAL XMA01 / YMA01 sitting.

Dijkstra's algorithm
Examiner keyword
An algorithm for finding the shortest path from a source vertex to every other vertex in a weighted graph with non-negative edge weights. At each step, assign a permanent label (final shortest distance) to the unvisited vertex with the smallest working label, then update its neighbours.
Working label
Examiner keyword
A tentative shortest-distance estimate at a vertex during Dijkstra. Updated whenever a better route is found. Replaced (or struck-through) by an improved estimate — never erased.
Permanent label
Examiner keyword
The final shortest distance from the source vertex. Assigned to vertices in INCREASING order of distance from the source. Once permanent, never changes.
Route inspection (Chinese postman)
Examiner keyword
Find a closed walk that traverses every edge AT LEAST ONCE with minimum total weight. Solution depends on the number of odd-degree vertices.
Eulerian graph
A connected graph in which every vertex has even degree. Equivalently: there exists a closed walk that traverses every edge exactly once.
Semi-Eulerian graph
A connected graph with exactly two odd-degree vertices. There exists an open walk (not returning to start) that traverses every edge exactly once.
Travelling Salesman Problem (TSP)
Examiner keyword
Find the shortest closed tour that visits every vertex exactly once. Edexcel D1 uses the 'classical' TSP — assumes a complete weighted graph (an edge between every pair of vertices, with triangle inequality).
Nearest-neighbour algorithm
Examiner keyword
Heuristic for TSP: start at a chosen vertex; always go to the nearest unvisited vertex; finally return to the start. Provides an UPPER BOUND. Different starting vertices give different bounds.
TSP lower bound
Examiner keyword
$\text{LB} = \text{MST}(G \setminus \{v\}) +$ (two shortest edges from $v$ ). Provides a lower bound for the optimal TSP tour length. Vertex choice affects tightness.

Common Mistakes and Misconceptions — Algorithms on graphs II

The traps other students keep falling into on algorithms on graphs ii questions — taken from recent Pearson Edexcel IAL XMA01 / YMA01 examiner reports and mark schemes — and how to avoid them.

✕Erasing replaced working labels instead of striking them through
WDM01/01 Examiner Reports — flagged every session
Why it happens
Keeping the page tidy.
How to avoid it
Edexcel mark schemes inspect EVERY working label. Strike replaced labels through; write the new label beside (or below). Never use rubber/eraser.
✕Assigning permanent labels in the wrong order
Why it happens
Confusing 'next vertex' with 'most recent neighbour'.
How to avoid it
Always pick the UNVISITED vertex with the SMALLEST working label as the next to assign a permanent label. Compare ALL working labels each step, not just neighbours of the most recent vertex.
✕Trying to apply route inspection without listing the degrees
Why it happens
Jumping to the algorithm.
How to avoid it
STEP 1 of route inspection is ALWAYS: list every vertex's degree and identify which are odd. The algorithm depends on the number of odd vertices ( $0, 2,$ or $\ge 4$ ).
✕Forgetting to return to the starting vertex in nearest-neighbour TSP
Why it happens
Algorithm 'ends' after the last vertex.
How to avoid it
A TSP TOUR is CLOSED — it must return to start. Always add the final return-edge weight.
✕Adding the two shortest edges from $v$ to the MST of the WHOLE graph (not the graph minus $v$ )
Why it happens
Forgetting to delete the chosen vertex.
How to avoid it
DELETE the chosen vertex FIRST, then compute the MST of what remains, then add the two shortest edges incident with the DELETED vertex.
✕Picking the two shortest edges in the entire graph instead of the two shortest from $v$
Why it happens
Misreading the procedure.
How to avoid it
Only edges INCIDENT WITH $v$ count for the +2 part. The MST and the 2 edges are joined at $v$ to make a closed structure.

Past paper style quiz

Get a report showing which sub-topics you've nailed and which ones still need work.

Algorithms on graphs II — frequently asked questions

The things students keep getting wrong in this sub-topic, answered.

Algorithms on graphs II

Detailed Notes

What you’ll learn

How it’s examined

1Dijkstra's shortest path (8 marks, D1)

2Route inspection: 2 odd vertices (6 marks, D1)

3Route inspection: 4 odd vertices (8 marks, D1)

4TSP upper bound by nearest neighbour (5 marks, D1)

5TSP lower bound via MST (6 marks, D1)

Dijkstra update rule

Route inspection (Chinese postman) with 2 odd vertices

TSP lower bound (delete-a-vertex method)

Dijkstra's algorithm

Working label

Permanent label

Route inspection (Chinese postman)

Eulerian graph

Semi-Eulerian graph

Travelling Salesman Problem (TSP)

Nearest-neighbour algorithm

TSP lower bound

✕Erasing replaced working labels instead of striking them through

✕Assigning permanent labels in the wrong order

✕Trying to apply route inspection without listing the degrees

✕Forgetting to return to the starting vertex in nearest-neighbour TSP

✕Adding the two shortest edges from vvv to the MST of the WHOLE graph (not the graph minus vvv)

✕Picking the two shortest edges in the entire graph instead of the two shortest from vvv

Past paper style quiz

Algorithms on graphs II — frequently asked questions

✕Adding the two shortest edges from $v$ to the MST of the WHOLE graph (not the graph minus $v$ )

✕Picking the two shortest edges in the entire graph instead of the two shortest from $v$