Further Maths Minimum spanning trees and shortest path Practice Questions

Free Further Maths Minimum spanning trees and shortest path practice questions with full step-by-step worked solutions. Covers kruskal, minimum-spanning-tree, networks, prim. Practise exam-style problems and check your method.

kruskalminimum-spanning-treenetworksprimtreesdijkstra
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
A network has vertices AA, BB, CC, DD and EE. The arcs of the network and their weights are AB=10AB=10, AC=16AC=16, BC=44BC=44, BD=17BD=17, CD=25CD=25, CE=45CE=45, DE=33DE=33. Use Kruskal's algorithm to find a minimum spanning tree for this network, and state the total weight of the tree.
Show worked solution

Worked solution

  1. List the arcs in ascending order of weight

    AB=10,  AC=16,  BD=17,  CD=25,  DE=33,  BC=44,  CE=45AB=10,\;AC=16,\;BD=17,\;CD=25,\;DE=33,\;BC=44,\;CE=45

    Kruskal's algorithm looks at the arcs in order of increasing weight.

  2. Work along the list, rejecting any arc that would create a cycle

    accept AB,  AC,  BD,  DE;reject CD\text{accept }AB,\;AC,\;BD,\;DE;\quad\text{reject }CD

    An arc is rejected exactly when both of its ends are already joined to each other by arcs already chosen.

  3. Add the weights of the arcs in the tree

    10+16+17+33=7610+16+17+33=76

    The total weight of the tree is the sum of the weights of its 44 arcs.

  4. State the total weight of the minimum spanning tree

    total weight=76\text{total weight}=76

    This is the smallest possible total weight of a spanning tree of this network.

Answer
7676
Question 2
2 markseasy
A network has vertices AA, BB, CC, DD and EE. The arcs of the network and their weights are AB=7AB=7, AC=4AC=4, AD=39AD=39, BC=30BC=30, BD=8BD=8, CD=6CD=6, DE=42DE=42. Use Dijkstra's algorithm to find the shortest route from AA to EE. Which of the following is the shortest route from AA to EE?
Show worked solution

Worked solution

  1. Give the start vertex AA a final label of 00 and label its neighbours

    final(A)=0temporary: B=7,  C=4,  D=39\text{final}(A)=0\quad\text{temporary: }B=7,\;C=4,\;D=39

    The working values at the neighbours of AA are the weights of the arcs leaving AA.

  2. Make the smallest temporary label permanent and repeat until every vertex has a final label

    final(A)=0,  final(C)=4,  final(B)=7,  final(D)=10,  final(E)=52\text{final}(A)=0,\;\text{final}(C)=4,\;\text{final}(B)=7,\;\text{final}(D)=10,\;\text{final}(E)=52

    The vertices become permanent in this order: A,\;C,\;B,\;D,\;E.

  3. Trace the route back from EE

    E←D←C←A(4+6+42=52)E\leftarrow D\leftarrow C\leftarrow A\quad\left(4+6+42=52\right)

    Working backwards, each arc used must reduce the final label by exactly its weight.

  4. Select the option giving the shortest route

    A→C→D→E(length 52)A\to C\to D\to E\quad\left(\text{length }52\right)

    Every other route from AA to EE is strictly longer.

Answer
A→C→D→EA\to C\to D\to E
Question 3
4 marksintermediate
A network has vertices AA, BB, CC, DD, EE and FF. The arcs of the network and their weights are AB=47AB=47, AC=34AC=34, AE=42AE=42, BC=9BC=9, BD=13BD=13, BE=10BE=10, BF=52BF=52, CD=19CD=19, DE=23DE=23. Prim's algorithm is applied, starting at AA. Which of the following gives the order in which the vertices are added to the tree?
Show worked solution

Worked solution

  1. Start the tree at vertex AA

    tree={A}\text{tree}=\left\{A\right\}

    Prim's algorithm grows a single connected tree from the starting vertex.

  2. Iteration 1: the cheapest arc from the tree to a new vertex is ACAC, so add vertex CC

    AC=34add Crunning total=34AC=34\quad\text{add }C\quad\text{running total}=34

    The candidate arcs were AC=34,\;AE=42,\;AB=47.

  3. Iteration 2: the cheapest arc from the tree to a new vertex is BCBC, so add vertex BB

    BC=9add Brunning total=43BC=9\quad\text{add }B\quad\text{running total}=43

    The candidate arcs were BC=9,\;CD=19,\;AE=42,\;AB=47.

  4. Iteration 3: the cheapest arc from the tree to a new vertex is BEBE, so add vertex EE

    BE=10add Erunning total=53BE=10\quad\text{add }E\quad\text{running total}=53

    The candidate arcs were BE=10,\;BD=13,\;CD=19,\;AE=42,\;BF=52.

  5. Iteration 4: the cheapest arc from the tree to a new vertex is BDBD, so add vertex DD

    BD=13add Drunning total=66BD=13\quad\text{add }D\quad\text{running total}=66

    The candidate arcs were BD=13,\;CD=19,\;DE=23,\;BF=52.

  6. Iteration 5: the cheapest arc from the tree to a new vertex is BFBF, so add vertex FF

    BF=52add Frunning total=118BF=52\quad\text{add }F\quad\text{running total}=118

    The candidate arcs were BF=52.

  7. Select the option giving the order in which the vertices join the tree

    order:  A,  C,  B,  E,  D,  F\text{order}:\;A,\;C,\;B,\;E,\;D,\;F

    The vertices join the tree in the order in which their arcs are chosen.

Answer
A,\;C,\;B,\;E,\;D,\;F
Question 4
6 markshard
A network has vertices AA, BB, CC, DD, EE, FF and GG. The arcs of the network and their weights are AB=2AB=2, AF=5AF=5, BC=45BC=45, BD=56BD=56, BF=18BF=18, CD=4CD=4, CE=25CE=25, CG=32CG=32, DE=16DE=16, DG=34DG=34, EG=7EG=7. Kruskal's algorithm is applied to this network. Which arc is the first to be rejected because it would create a cycle?
Show worked solution

Worked solution

  1. List the arcs in ascending order of weight

    AB=2,  CD=4,  AF=5,  EG=7,  DE=16,  BF=18,  CE=25,  CG=32,  DG=34,  BC=45,  BD=56AB=2,\;CD=4,\;AF=5,\;EG=7,\;DE=16,\;BF=18,\;CE=25,\;CG=32,\;DG=34,\;BC=45,\;BD=56

    Kruskal's algorithm looks at the arcs in order of increasing weight.

  2. Consider arc ABAB: its ends are in different components, so accept it

    AB=2acceptrunning total=2AB=2\quad\text{accept}\quad\text{running total}=2

    Accepting this arc joins two separate parts of the forest.

  3. Consider arc CDCD: its ends are in different components, so accept it

    CD=4acceptrunning total=6CD=4\quad\text{accept}\quad\text{running total}=6

    Accepting this arc joins two separate parts of the forest.

  4. Consider arc AFAF: its ends are in different components, so accept it

    AF=5acceptrunning total=11AF=5\quad\text{accept}\quad\text{running total}=11

    Accepting this arc joins two separate parts of the forest.

  5. Consider arc EGEG: its ends are in different components, so accept it

    EG=7acceptrunning total=18EG=7\quad\text{accept}\quad\text{running total}=18

    Accepting this arc joins two separate parts of the forest.

  6. Consider arc DEDE: its ends are in different components, so accept it

    DE=16acceptrunning total=34DE=16\quad\text{accept}\quad\text{running total}=34

    Accepting this arc joins two separate parts of the forest.

  7. Consider arc BFBF: both ends are already connected, so reject it

    BF=18reject (cycle)BF=18\quad\text{reject (cycle)}

    Adding this arc would close a cycle, which a tree may not contain.

  8. Consider arc CECE: both ends are already connected, so reject it

    CE=25reject (cycle)CE=25\quad\text{reject (cycle)}

    Adding this arc would close a cycle, which a tree may not contain.

  9. Consider arc CGCG: both ends are already connected, so reject it

    CG=32reject (cycle)CG=32\quad\text{reject (cycle)}

    Adding this arc would close a cycle, which a tree may not contain.

  10. Consider arc DGDG: both ends are already connected, so reject it

    DG=34reject (cycle)DG=34\quad\text{reject (cycle)}

    Adding this arc would close a cycle, which a tree may not contain.

  11. Consider arc BCBC: its ends are in different components, so accept it

    BC=45acceptrunning total=79BC=45\quad\text{accept}\quad\text{running total}=79

    Accepting this arc joins two separate parts of the forest.

  12. Stop: the tree now has n−1n-1 arcs

    arcs=6=7−1\text{arcs}=6=7-1

    A spanning tree on 77 vertices has exactly 66 arcs, so the algorithm terminates.

  13. Add the weights of the arcs in the tree

    2+4+5+7+16+45=792+4+5+7+16+45=79

    The minimum spanning tree is AB,\;CD,\;AF,\;EG,\;DE,\;BC.

  14. Select the first arc that Kruskal's algorithm rejects

    BF=18(would create a cycle)BF=18\quad\text{(would create a cycle)}

    This is the first arc in the sorted list whose two ends are already connected to one another.

Answer
BF=18BF=18
Question 5
9 markschallenging
A network has vertices AA, BB, CC, DD, EE, FF, GG and HH. The arcs of the network and their weights are AB=53AB=53, AD=44AD=44, BC=27BC=27, BD=36BD=36, BG=25BG=25, CD=54CD=54, CG=38CG=38, DE=28DE=28, DF=3DF=3, EG=10EG=10, EH=22EH=22, FG=21FG=21, FH=49FH=49. Kruskal's algorithm is used to find a minimum spanning tree. Which of the following gives the order in which the arcs are added to the tree?
Show worked solution

Worked solution

  1. List the arcs in ascending order of weight

    DF=3,  EG=10,  FG=21,  EH=22,  BG=25,  BC=27,  DE=28,  BD=36,  CG=38,  AD=44,  FH=49,  AB=53,  CD=54DF=3,\;EG=10,\;FG=21,\;EH=22,\;BG=25,\;BC=27,\;DE=28,\;BD=36,\;CG=38,\;AD=44,\;FH=49,\;AB=53,\;CD=54

    Kruskal's algorithm looks at the arcs in order of increasing weight.

  2. Consider arc DFDF: its ends are in different components, so accept it

    DF=3acceptrunning total=3DF=3\quad\text{accept}\quad\text{running total}=3

    Accepting this arc joins two separate parts of the forest.

  3. Consider arc EGEG: its ends are in different components, so accept it

    EG=10acceptrunning total=13EG=10\quad\text{accept}\quad\text{running total}=13

    Accepting this arc joins two separate parts of the forest.

  4. Consider arc FGFG: its ends are in different components, so accept it

    FG=21acceptrunning total=34FG=21\quad\text{accept}\quad\text{running total}=34

    Accepting this arc joins two separate parts of the forest.

  5. Consider arc EHEH: its ends are in different components, so accept it

    EH=22acceptrunning total=56EH=22\quad\text{accept}\quad\text{running total}=56

    Accepting this arc joins two separate parts of the forest.

  6. Consider arc BGBG: its ends are in different components, so accept it

    BG=25acceptrunning total=81BG=25\quad\text{accept}\quad\text{running total}=81

    Accepting this arc joins two separate parts of the forest.

  7. Consider arc BCBC: its ends are in different components, so accept it

    BC=27acceptrunning total=108BC=27\quad\text{accept}\quad\text{running total}=108

    Accepting this arc joins two separate parts of the forest.

  8. Consider arc DEDE: both ends are already connected, so reject it

    DE=28reject (cycle)DE=28\quad\text{reject (cycle)}

    Adding this arc would close a cycle, which a tree may not contain.

  9. Consider arc BDBD: both ends are already connected, so reject it

    BD=36reject (cycle)BD=36\quad\text{reject (cycle)}

    Adding this arc would close a cycle, which a tree may not contain.

  10. Consider arc CGCG: both ends are already connected, so reject it

    CG=38reject (cycle)CG=38\quad\text{reject (cycle)}

    Adding this arc would close a cycle, which a tree may not contain.

  11. Consider arc ADAD: its ends are in different components, so accept it

    AD=44acceptrunning total=152AD=44\quad\text{accept}\quad\text{running total}=152

    Accepting this arc joins two separate parts of the forest.

  12. Stop: the tree now has n−1n-1 arcs

    arcs=7=8−1\text{arcs}=7=8-1

    A spanning tree on 88 vertices has exactly 77 arcs, so the algorithm terminates.

  13. Add the weights of the arcs in the tree

    3+10+21+22+25+27+44=1523+10+21+22+25+27+44=152

    The minimum spanning tree is DF,\;EG,\;FG,\;EH,\;BG,\;BC,\;AD.

  14. Cross-check the tree with Prim's algorithm

    Prim:  AD,  DF,  FG,  EG,  EH,  BG,  BCtotal=152\text{Prim}:\;AD,\;DF,\;FG,\;EG,\;EH,\;BG,\;BC\quad\text{total}=152

    Kruskal's and Prim's algorithms must produce the same minimum spanning tree, so this is a strong check on the answer.

  15. Select the option giving Kruskal's order of insertion

    order:  DF,  EG,  FG,  EH,  BG,  BC,  AD\text{order}:\;DF,\;EG,\;FG,\;EH,\;BG,\;BC,\;AD

    The weights are all different, so this order is the only possible one.

Answer
DF,\;EG,\;FG,\;EH,\;BG,\;BC,\;AD

Unlock 65 more Minimum spanning trees and shortest path questions

Create a free account to work through every Further Maths Minimum spanning trees and shortest path question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Minimum spanning trees and shortest path practice

Hard QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks