Practice questions covering algorithms on graphs from this specification. Attempt the questions below; real-paper references for this topic are being imported.
Questions to attempt
6 questions on Algorithms on graphs, each with its mark scheme and worked method. Reveal the answer when you have had a go.
D1-2.1 · The minimum spanning tree (minimum connector) problem. Prim's and Kruskal's algorithm.
Q1
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
1.
A network has vertices A to F and arcs AB=9, AC=5, AD=12, BC=7, BE=8, CD=6, CE=11, CF=13, DF=10, EF=4. Use Prim's algorithm starting at A to find a minimum spanning tree, stating the arcs in the order they are added and the total weight.
(6)
(Total for Question 1 is 6 marks)
D1-2.1 · The minimum spanning tree (minimum connector) problem. Prim's and Kruskal's algorithm.
Q2
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
2.
A network has vertices A, B, C, D, E and arcs AB=6, AC=4, BC=3, BD=9, CD=5, CE=8, DE=7. Use Kruskal's algorithm to find a minimum spanning tree, listing the arcs in the order you consider them, and state its total weight.
(5)
(Total for Question 2 is 5 marks)
D1-2.1 · The minimum spanning tree (minimum connector) problem. Prim's and Kruskal's algorithm.
Q3
ORIGINAL
Year 1
Year 1: this is the AS subject content the exam board publishes, which is what most schools teach in Year 12.
3.
Apply Prim's algorithm starting at A to the network with vertices A to G and arcs AB=14, AC=10, AD=17, BC=8, BE=13, CD=9, CE=16, CF=21, DF=12, EF=7, EG=19, FG=11. State the order in which the vertices join the tree, the arcs used, and verify that the weight agrees with Kruskal's answer of 57.
(7)
(Total for Question 3 is 7 marks)
D1-2.2 · Dijkstra's and Floyd's algorithm for finding the shortest path.
Q4
ORIGINAL
Years 1 and 2
Years 1 and 2: this holds AS subject content and content the exam board adds beyond it for the full A-level.
4.
A network has vertices A to F and arcs AB=5, AC=8, BC=2, BD=9, CD=4, CE=7, DF=6, EF=4. Use Dijkstra's algorithm from A to complete every box and find the shortest route from A to F.
(7)
(Total for Question 4 is 7 marks)
D1-2.2 · Dijkstra's and Floyd's algorithm for finding the shortest path.
Q5
ORIGINAL
Years 1 and 2
Years 1 and 2: this holds AS subject content and content the exam board adds beyond it for the full A-level.
5.
A network has vertices A, B, C, D, E and arcs AB=4, AC=7, BC=2, BD=8, CD=3, CE=9, DE=5. Use Dijkstra's algorithm from A to find the final label of every vertex and the shortest path from A to E.
(6)
(Total for Question 5 is 6 marks)
D1-2.2 · Dijkstra's and Floyd's algorithm for finding the shortest path.
Q6
ORIGINAL
Years 1 and 2
Years 1 and 2: this holds AS subject content and content the exam board adds beyond it for the full A-level.
6.
For the network on A, B, C, D with AB=7, AD=4, BC=3, CD=2 and no direct arcs AC or BD, complete Floyd's algorithm and write down the final distance matrix and final route matrix. Use them to state the shortest route from A to C and from B to D.
(8)
(Total for Question 6 is 8 marks)
Progress is saved on this device for guests and accounts right now; cross-device account sync is not live yet.
Real-paper references for this module are being imported — the questions above are the site's own, exam-faithful, marked.
Reference rows contain series, paper, question number, marks and classification metadata only. Pearson's question papers open on Pearson's own website.
Stuck on algorithms on graphs?
Everything here stays free. If algorithms on graphs is where the marks keep going, I teach it one to one from the mark schemes. Free intro call, then a free first lesson.