Worked question 4 - Decision: Algorithms and Graph Theory Depth
Problem 1: connect every town to the depot using cable of minimum total length (the towns do not need to be able to reach each other quickly afterwards, only to be linked into a single network).
Problem 2: find the quickest possible route for a single van to drive from the depot to one specific town.
Problem 3: find the shortest possible route for a gritting lorry that must drive along every road in the network at least once, starting and finishing at the depot.
Discuss which type of algorithm, a minimum spanning tree algorithm (Kruskal's or Prim's), Dijkstra's algorithm, or the route inspection algorithm, should be used to solve each problem. Your answer should explain what feature of each problem identifies the correct technique, and explain why using an incorrect technique would fail to answer the question actually being asked.
Answer and mark scheme
Question 4
| Credit | Answer or working |
|---|---|
| 0 | Level 0 No relevant technique correctly matched to any of the three problems, or the response does not address the question. |
| 1-2 | Level 1 At least one problem is matched to a broadly appropriate technique, but with little or no valid justification, and no discussion of why other techniques would be unsuitable. |
| 3-4 | Level 2 At least two of the three problems are correctly matched to their appropriate technique, with some valid justification referring to what each problem requires; explanation of why an incorrect technique would fail is limited or only partially developed. |
| 5-6 | Level 3 All three problems are correctly matched to their appropriate technique (minimum spanning tree algorithm for Problem 1, Dijkstra's algorithm for Problem 2, route inspection algorithm for Problem 3), with clear justification referring to the specific requirement of each problem, and a clear explanation of why using an incorrect technique for a given problem would fail to answer the question actually being asked. |
- Indicative content:
- Problem 1 only requires every town to be linked into a single connected network using the least total length of cable, with no requirement to travel quickly between any two particular towns afterwards; this is a minimum spanning tree problem, solved using Kruskal's algorithm or Prim's algorithm.
- Problem 2 requires the shortest route between two specific vertices only (the depot and one named town); this is exactly what Dijkstra's algorithm finds.
- Problem 3 requires a route that uses every road in the network at least once and returns to its starting point; this is the route inspection (Chinese postman) problem.
- Using Dijkstra's algorithm for Problem 1 would only ever find a path between two particular vertices, not a structure connecting every town together, so it cannot solve Problem 1.
- Using a minimum spanning tree for Problem 2 would not generally give the shortest route between the depot and a specific town, since a spanning tree minimises the total length of the whole network, not the distance between any one particular pair of vertices; the route between two towns within a minimum spanning tree can be much longer than the true shortest path between them.
- Using a minimum spanning tree, or Dijkstra's algorithm, for Problem 3 would not guarantee that every road is used: a spanning tree deliberately omits some edges (it has only n - 1 edges for n vertices), and Dijkstra's algorithm only ever finds a route between two vertices, not a route covering every edge.
- The key skill is recognising the single feature that identifies each type of problem: connect everything as cheaply as possible (minimum spanning tree); find the shortest distance between two specific vertices (Dijkstra's algorithm); or use every edge at least once (route inspection algorithm).
Answer: Open response; assessed against the levels of response criteria above using the indicative content as a guide.





