Hard Further Maths Minimum spanning trees and shortest path Questions

Challenging, exam-style Further Maths Minimum spanning trees and shortest path questions with worked solutions. Stretch yourself on the hardest kruskal, minimum-spanning-tree, networks, prim problems.

kruskalminimum-spanning-treenetworksprimdistance-matrixdijkstra
Further Maths34 questionsStep-by-step solutions
Question 1
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
Question 2
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=49AB=49, AE=14AE=14, AF=22AF=22, AG=28AG=28, BC=8BC=8, BE=9BE=9, BF=40BF=40, CD=30CD=30, CF=44CF=44, CH=33CH=33, DE=53DE=53, DF=4DF=4, GH=38GH=38. Dijkstra's algorithm is applied, starting at AA. Which of the following gives the order in which the vertices receive their final labels?
Show worked solution

Worked solution

  1. Vertex AA has the smallest temporary label, so make it permanent with final label 00

    final(A)=0update: B=49,  E=14,  F=22,  G=28\text{final}(A)=0\quad\text{update: }B=49,\;E=14,\;F=22,\;G=28

    Its neighbours' working values are replaced only if the new value is smaller.

  2. Vertex EE has the smallest temporary label, so make it permanent with final label 1414

    final(E)=14update: B=23,  D=67\text{final}(E)=14\quad\text{update: }B=23,\;D=67

    Its neighbours' working values are replaced only if the new value is smaller.

  3. Vertex FF has the smallest temporary label, so make it permanent with final label 2222

    final(F)=22update: C=66,  D=26\text{final}(F)=22\quad\text{update: }C=66,\;D=26

    Its neighbours' working values are replaced only if the new value is smaller.

  4. Vertex BB has the smallest temporary label, so make it permanent with final label 2323

    final(B)=23update: C=31\text{final}(B)=23\quad\text{update: }C=31

    Its neighbours' working values are replaced only if the new value is smaller.

  5. Vertex DD has the smallest temporary label, so make it permanent with final label 2626

    final(D)=26no labels improved\text{final}(D)=26\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  6. Vertex GG has the smallest temporary label, so make it permanent with final label 2828

    final(G)=28update: H=66\text{final}(G)=28\quad\text{update: }H=66

    Its neighbours' working values are replaced only if the new value is smaller.

  7. Vertex CC has the smallest temporary label, so make it permanent with final label 3131

    final(C)=31update: H=64\text{final}(C)=31\quad\text{update: }H=64

    Its neighbours' working values are replaced only if the new value is smaller.

  8. Vertex HH has the smallest temporary label, so make it permanent with final label 6464

    final(H)=64no labels improved\text{final}(H)=64\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  9. List the order in which the vertices became permanent

    A,\;E,\;F,\;B,\;D,\;G,\;C,\;H

    The final labels are all different, so this order is unique.

  10. Confirm that the shortest route is unique

    next best route A→G→H  has weight 66>64\text{next best route }A\to G\to H\;\text{has weight }66>64

    No other route from AA to HH achieves the minimum, so the shortest route is unique.

  11. List the final labels of all the vertices

    A=0,  B=23,  C=31,  D=26,  E=14,  F=22,  G=28,  H=64A=0,\;B=23,\;C=31,\;D=26,\;E=14,\;F=22,\;G=28,\;H=64

    Each final label is the length of the shortest path from AA to that vertex.

  12. Recall how Dijkstra's algorithm works

    make the smallest temporary label permanent, then update its neighbours\text{make the smallest temporary label permanent, then update its neighbours}

    The vertex with the smallest temporary label can never be improved, so it may be made permanent.

  13. Note that a temporary label is only ever replaced by a smaller value

    temp(X)←min⁡{temp(X),  final(Y)+w(YX)}\text{temp}(X)\leftarrow\min\left\{\text{temp}(X),\;\text{final}(Y)+w(YX)\right\}

    A working value is crossed out and rewritten only when a shorter route to that vertex is found.

  14. Note that Dijkstra's algorithm requires non-negative weights

    w≥0w\geq 0

    All the arc weights here are positive, so the algorithm is valid.

  15. Select the option giving the order of the final labels

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

    Vertices receive their final labels in increasing order of those labels.

Answer
A,\;E,\;F,\;B,\;D,\;G,\;C,\;H
Question 3
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=3AB=3, AC=35AC=35, AE=17AE=17, BC=46BC=46, BE=10BE=10, BF=2BF=2, BG=29BG=29, CD=5CD=5, CE=20CE=20, CF=11CF=11, CG=27CG=27, EH=58EH=58, FG=59FG=59. Dijkstra's algorithm is applied, starting at AA. Which of the following gives the order in which the vertices receive their final labels?
Show worked solution

Worked solution

  1. Vertex AA has the smallest temporary label, so make it permanent with final label 00

    final(A)=0update: B=3,  C=35,  E=17\text{final}(A)=0\quad\text{update: }B=3,\;C=35,\;E=17

    Its neighbours' working values are replaced only if the new value is smaller.

  2. Vertex BB has the smallest temporary label, so make it permanent with final label 33

    final(B)=3update: E=13,  F=5,  G=32\text{final}(B)=3\quad\text{update: }E=13,\;F=5,\;G=32

    Its neighbours' working values are replaced only if the new value is smaller.

  3. Vertex FF has the smallest temporary label, so make it permanent with final label 55

    final(F)=5update: C=16\text{final}(F)=5\quad\text{update: }C=16

    Its neighbours' working values are replaced only if the new value is smaller.

  4. Vertex EE has the smallest temporary label, so make it permanent with final label 1313

    final(E)=13update: H=71\text{final}(E)=13\quad\text{update: }H=71

    Its neighbours' working values are replaced only if the new value is smaller.

  5. Vertex CC has the smallest temporary label, so make it permanent with final label 1616

    final(C)=16update: D=21\text{final}(C)=16\quad\text{update: }D=21

    Its neighbours' working values are replaced only if the new value is smaller.

  6. Vertex DD has the smallest temporary label, so make it permanent with final label 2121

    final(D)=21no labels improved\text{final}(D)=21\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  7. Vertex GG has the smallest temporary label, so make it permanent with final label 3232

    final(G)=32no labels improved\text{final}(G)=32\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  8. Vertex HH has the smallest temporary label, so make it permanent with final label 7171

    final(H)=71no labels improved\text{final}(H)=71\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  9. List the order in which the vertices became permanent

    A,\;B,\;F,\;E,\;C,\;D,\;G,\;H

    The final labels are all different, so this order is unique.

  10. Confirm that the shortest route is unique

    next best route A→E→H  has weight 75>71\text{next best route }A\to E\to H\;\text{has weight }75>71

    No other route from AA to HH achieves the minimum, so the shortest route is unique.

  11. List the final labels of all the vertices

    A=0,  B=3,  C=16,  D=21,  E=13,  F=5,  G=32,  H=71A=0,\;B=3,\;C=16,\;D=21,\;E=13,\;F=5,\;G=32,\;H=71

    Each final label is the length of the shortest path from AA to that vertex.

  12. Recall how Dijkstra's algorithm works

    make the smallest temporary label permanent, then update its neighbours\text{make the smallest temporary label permanent, then update its neighbours}

    The vertex with the smallest temporary label can never be improved, so it may be made permanent.

  13. Note that a temporary label is only ever replaced by a smaller value

    temp(X)←min⁡{temp(X),  final(Y)+w(YX)}\text{temp}(X)\leftarrow\min\left\{\text{temp}(X),\;\text{final}(Y)+w(YX)\right\}

    A working value is crossed out and rewritten only when a shorter route to that vertex is found.

  14. Note that Dijkstra's algorithm requires non-negative weights

    w≥0w\geq 0

    All the arc weights here are positive, so the algorithm is valid.

  15. Select the option giving the order of the final labels

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

    Vertices receive their final labels in increasing order of those labels.

Answer
A,\;B,\;F,\;E,\;C,\;D,\;G,\;H
Question 4
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=44AB=44, AE=25AE=25, AF=16AF=16, BC=17BC=17, BD=27BD=27, BE=23BE=23, CE=37CE=37, CF=50CF=50, CG=47CG=47, DE=41DE=41, DF=42DF=42, EG=43EG=43, GH=24GH=24. Use Dijkstra's algorithm to find the shortest route from AA to HH. Which of the following is the shortest route from AA to HH?
Show worked solution

Worked solution

  1. Vertex AA has the smallest temporary label, so make it permanent with final label 00

    final(A)=0update: B=44,  E=25,  F=16\text{final}(A)=0\quad\text{update: }B=44,\;E=25,\;F=16

    Its neighbours' working values are replaced only if the new value is smaller.

  2. Vertex FF has the smallest temporary label, so make it permanent with final label 1616

    final(F)=16update: C=66,  D=58\text{final}(F)=16\quad\text{update: }C=66,\;D=58

    Its neighbours' working values are replaced only if the new value is smaller.

  3. Vertex EE has the smallest temporary label, so make it permanent with final label 2525

    final(E)=25update: C=62,  G=68\text{final}(E)=25\quad\text{update: }C=62,\;G=68

    Its neighbours' working values are replaced only if the new value is smaller.

  4. Vertex BB has the smallest temporary label, so make it permanent with final label 4444

    final(B)=44update: C=61\text{final}(B)=44\quad\text{update: }C=61

    Its neighbours' working values are replaced only if the new value is smaller.

  5. Vertex DD has the smallest temporary label, so make it permanent with final label 5858

    final(D)=58no labels improved\text{final}(D)=58\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  6. Vertex CC has the smallest temporary label, so make it permanent with final label 6161

    final(C)=61no labels improved\text{final}(C)=61\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  7. Vertex GG has the smallest temporary label, so make it permanent with final label 6868

    final(G)=68update: H=92\text{final}(G)=68\quad\text{update: }H=92

    Its neighbours' working values are replaced only if the new value is smaller.

  8. Vertex HH has the smallest temporary label, so make it permanent with final label 9292

    final(H)=92no labels improved\text{final}(H)=92\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  9. Read off the final label at HH

    final(H)=92\text{final}(H)=92

    The final label is the length of the shortest path from AA.

  10. Trace the shortest route backwards from HH

    H←G←E←AH\leftarrow G\leftarrow E\leftarrow A

    At each stage the arc used reduces the final label by exactly its own weight.

  11. Check the route by adding its arc weights

    25+43+24=9225+43+24=92

    The weights along the route add up to the final label, as they must.

  12. Confirm that the shortest route is unique

    next best route A→B→C→G→H  has weight 132>92\text{next best route }A\to B\to C\to G\to H\;\text{has weight }132>92

    No other route from AA to HH achieves the minimum, so the shortest route is unique.

  13. List the final labels of all the vertices

    A=0,  B=44,  C=61,  D=58,  E=25,  F=16,  G=68,  H=92A=0,\;B=44,\;C=61,\;D=58,\;E=25,\;F=16,\;G=68,\;H=92

    Each final label is the length of the shortest path from AA to that vertex.

  14. List the order in which the vertices became permanent

    A,\;F,\;E,\;B,\;D,\;C,\;G,\;H

    The vertices are made permanent in increasing order of their final labels.

  15. Select the option giving the shortest route

    A→E→G→H(length 92)A\to E\to G\to H\quad\left(\text{length }92\right)

    Every other route from AA to HH is strictly longer.

Answer
A→E→G→HA\to E\to G\to H
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=37AB=37, AE=35AE=35, AF=17AF=17, BC=19BC=19, BD=26BD=26, BE=29BE=29, CD=51CD=51, CG=49CG=49, DE=25DE=25, EF=33EF=33, EH=50EH=50, FG=46FG=46, GH=9GH=9. Use Dijkstra's algorithm to find the shortest route from AA to HH. Which of the following is the shortest route from AA to HH?
Show worked solution

Worked solution

  1. Vertex AA has the smallest temporary label, so make it permanent with final label 00

    final(A)=0update: B=37,  E=35,  F=17\text{final}(A)=0\quad\text{update: }B=37,\;E=35,\;F=17

    Its neighbours' working values are replaced only if the new value is smaller.

  2. Vertex FF has the smallest temporary label, so make it permanent with final label 1717

    final(F)=17update: G=63\text{final}(F)=17\quad\text{update: }G=63

    Its neighbours' working values are replaced only if the new value is smaller.

  3. Vertex EE has the smallest temporary label, so make it permanent with final label 3535

    final(E)=35update: D=60,  H=85\text{final}(E)=35\quad\text{update: }D=60,\;H=85

    Its neighbours' working values are replaced only if the new value is smaller.

  4. Vertex BB has the smallest temporary label, so make it permanent with final label 3737

    final(B)=37update: C=56\text{final}(B)=37\quad\text{update: }C=56

    Its neighbours' working values are replaced only if the new value is smaller.

  5. Vertex CC has the smallest temporary label, so make it permanent with final label 5656

    final(C)=56no labels improved\text{final}(C)=56\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  6. Vertex DD has the smallest temporary label, so make it permanent with final label 6060

    final(D)=60no labels improved\text{final}(D)=60\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  7. Vertex GG has the smallest temporary label, so make it permanent with final label 6363

    final(G)=63update: H=72\text{final}(G)=63\quad\text{update: }H=72

    Its neighbours' working values are replaced only if the new value is smaller.

  8. Vertex HH has the smallest temporary label, so make it permanent with final label 7272

    final(H)=72no labels improved\text{final}(H)=72\quad\text{no labels improved}

    Its neighbours' working values are replaced only if the new value is smaller.

  9. Read off the final label at HH

    final(H)=72\text{final}(H)=72

    The final label is the length of the shortest path from AA.

  10. Trace the shortest route backwards from HH

    H←G←F←AH\leftarrow G\leftarrow F\leftarrow A

    At each stage the arc used reduces the final label by exactly its own weight.

  11. Check the route by adding its arc weights

    17+46+9=7217+46+9=72

    The weights along the route add up to the final label, as they must.

  12. Confirm that the shortest route is unique

    next best route A→E→H  has weight 85>72\text{next best route }A\to E\to H\;\text{has weight }85>72

    No other route from AA to HH achieves the minimum, so the shortest route is unique.

  13. List the final labels of all the vertices

    A=0,  B=37,  C=56,  D=60,  E=35,  F=17,  G=63,  H=72A=0,\;B=37,\;C=56,\;D=60,\;E=35,\;F=17,\;G=63,\;H=72

    Each final label is the length of the shortest path from AA to that vertex.

  14. List the order in which the vertices became permanent

    A,\;F,\;E,\;B,\;C,\;D,\;G,\;H

    The vertices are made permanent in increasing order of their final labels.

  15. Select the option giving the shortest route

    A→F→G→H(length 72)A\to F\to G\to H\quad\left(\text{length }72\right)

    Every other route from AA to HH is strictly longer.

Answer
A→F→G→HA\to F\to G\to H

Unlock 29 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

Practice QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks