Dijkstra's algorithm

Dijkstra's algorithm Test

Spec 2.2 · Edexcel International A Level Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel International A Level Maths

Dijkstra's algorithm

Total 27 marks

Name

Class

Date

  1. 1
    A network has five vertices SS, AA, BB, CC and TT. The arcs and their lengths are SA=9SA=9, SB=5SB=5, AB=3AB=3, AC=10AC=10, BC=2BC=2, BT=9BT=9 and CT=6CT=6. Dijkstra's algorithm is applied starting at SS.
    (a)
    Which vertex is permanently labelled third, counting SS as the first?
    [1 mark]
    • AAA
    • BBB
    • CTT
    • DCC
    (b)
    What is the length of the shortest route from SS to TT?
    [1 mark]
    • A1313
    • B1414
    • C2020
    • D2525
    (c)
    Find the shortest route from SS to AA and its length. Explain why the arc SASA is not used.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    A network has six vertices AA to FF. The arcs and their lengths are AB=2AB=2, AC=8AC=8, AD=9AD=9, BC=13BC=13, BE=5BE=5, CD=13CD=13, CE=14CE=14, DF=6DF=6 and EF=4EF=4. Dijkstra's algorithm is applied starting at AA.
    (a)
    Which vertex is permanently labelled fourth, counting AA as the first?
    [1 mark]
    • ABB
    • BCC
    • CDD
    • DEE
    (b)
    What is the shortest distance from AA to DD?
    [1 mark]
    • A88
    • B1717
    • C99
    • D2121
    (c)
    Find the shortest route from AA to FF and state its length.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    A courier company has six depots AA to FF. The direct roads between depots and their lengths in km are AB=4AB=4, AC=3AC=3, AD=11AD=11, BC=10BC=10, BE=5BE=5, CD=13CD=13, CE=7CE=7, DF=13DF=13 and EF=12EF=12. A courier travels from AA to FF.
    (a)
    Use Dijkstra's algorithm to find the shortest route from AA to FF. State the order in which the vertices are permanently labelled, with their final labels, and the length of the route.
    [3 marks]
    (b)
    A new road is built directly between CC and FF of length xx km. Find the greatest integer value of xx for which the new road makes the shortest distance from AA to FF shorter than it is at present.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    A network of roads joins seven towns SS, AA, BB, CC, DD, EE and TT. The roads and their lengths in km are SA=9SA=9, SB=8SB=8, SC=15SC=15, AB=14AB=14, AD=11AD=11, BC=5BC=5, BE=7BE=7, CD=4CD=4, CE=14CE=14, DE=5DE=5, DT=6DT=6 and ET=10ET=10. An emergency vehicle must travel from SS to TT by the shortest route.
    (a)
    Use Dijkstra's algorithm to find the shortest route from SS to TT. State the order in which vertices are permanently labelled, with their final values, show where any working value is replaced, and give the route and its length.
    [6 marks]
    (b)
    The road CDCD is closed for repairs. Find the new shortest route from SS to TT, and the extra distance the vehicle must now travel.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests