Dijkstra's algorithm

Dijkstra's algorithm Test

Spec 2.2 · Edexcel A-Level Further 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 A-Level Further Maths

Dijkstra's algorithm

Total 27 marks

Name

Class

Date

  1. 1
    A road network joins a depot SS to a warehouse TT through four junctions AA, BB, CC and DD. The roads and their lengths in km are SA=4SA=4, SB=7SB=7, AB=2AB=2, AC=6AC=6, BC=3BC=3, BD=8BD=8, CD=6CD=6, CT=8CT=8 and DT=4DT=4. Dijkstra's algorithm is used to find the shortest route from SS to TT.
    (a)
    What is the final label of vertex BB?
    [1 mark]
    • A77
    • B22
    • C66
    • D99
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Which is the shortest route from SS to TT and its length?
    [1 mark]
    • AS−B−D−TS-B-D-T, 19 km
    • BS−A−C−TS-A-C-T, 18 km
    • CS−B−C−TS-B-C-T, 18 km
    • DS−A−B−C−TS-A-B-C-T, 17 km
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Explain why the final label at BB is 6 and not 7.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: after AA is labelled 4, the route S−A−BS-A-B gives 4+2=64+2=6
    A1: 6 is less than the working value 7 from the direct road
    SBSB, so 7 is replaced by 6
    Accept: the route via
    AA is shorter than the direct road

    Total for question 1: 4 marks

  2. 2
    Six towns AA to FF are joined by roads with lengths in km: AB=5AB=5, AC=8AC=8, BC=2BC=2, BD=9BD=9, CD=4CD=4, CE=9CE=9, DE=3DE=3, DF=10DF=10 and EF=6EF=6. Dijkstra's algorithm is used starting from AA.
    (a)
    Counting AA as the first, which vertex receives the fourth permanent label?
    [1 mark]
    • ADD
    • BCC
    • CEE
    • DFF
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    What is the final label of FF?
    [1 mark]
    • A2121
    • B2020
    • C2323
    • D2424
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Use the labels to find the shortest route from AA to FF and show how you worked it out.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: working back from FF (20): EE (14) because 14+6=2014+6=20, then DD (11) because 11+3=1411+3=14, CC (7) because 7+4=117+4=11, BB (5) because 5+2=75+2=7
    A1:
    A−B−C−D−E−FA-B-C-D-E-F
    Accept: a trace back using the working values rather than the sums

    Total for question 2: 4 marks

  3. 3
    A courier network has seven vertices SS, AA, BB, CC, DD, XX and TT. The roads and their lengths in km are SA=8SA=8, SC=12SC=12, AC=3AC=3, AX=11AX=11, BC=2BC=2, BD=6BD=6, BT=10BT=10, CD=7CD=7, CT=5CT=5, DX=9DX=9 and XT=4XT=4.
    (a)
    Apply Dijkstra's algorithm from SS. Show the working values at CC, and state the permanent labels of the next three vertices to be labelled after SS.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: AA labelled first with 8 (the smaller of SA=8SA=8 and SC=12SC=12)
    B1:
    CC has working values 12 then 8+3=118+3=11, so its label is 11
    B1:
    BB labelled next with 11+2=1311+2=13
    Do not accept:
    C=12C=12
    (b)
    A courier must travel from SS to TT and must call at XX. Find the shortest such route and its length.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: shortest route from SS to XX found by the algorithm: working values at XX are 19, 20 and 27
    A1:
    S−A−XS-A-X of length 19 km
    M1: add the shortest route from
    XX to TT, the road XT=4XT=4
    A1:
    S−A−X−TS-A-X-T of length 19+4=2319+4=23 km
    Accept: any correct working that shows the labels at
    XX

    Total for question 3: 7 marks

  4. 4
    A delivery network has eight vertices SS, AA, BB, CC, DD, EE, FF and TT. The roads and their lengths in km are SD=3SD=3, SF=6SF=6, AB=17AB=17, AD=14AD=14, AT=13AT=13, BC=15BC=15, BD=9BD=9, BE=8BE=8, BF=11BF=11, BT=16BT=16, CF=18CF=18, EF=19EF=19 and ET=2ET=2.
    (a)
    Use Dijkstra's algorithm to find the shortest route from SS to TT. Give the vertices in the order they are labelled, with their final labels, and state the route and its length.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: starts at SS (0), working values D=3D=3 and F=6F=6; DD labelled first
    A1: order of labelling
    SS, DD, FF, BB with labels 0, 3, 6, 12
    A1:
    B=12B=12 (via DD), not 17 via FF
    M1:
    EE has working values 25 (via FF) then 12+8=2012+8=20 (via BB), which replaces it
    A1: then
    A=17A=17, E=20E=20, T=22T=22 (working values for TT were 28 and 30)
    A1: route
    S−D−B−E−TS-D-B-E-T, length 22 km
    Accept: a trace back from
    TT using the labels
    (b)
    The road BEBE is closed. Explain why the labels of DD, FF, BB and AA do not change, find the new shortest route from SS to TT, and state how much longer it is.
    [6 marks]
    Show the mark scheme

    Mark scheme

    R1: DD, FF, BB and AA were all labelled before EE and their shortest routes do not use BEBE, so their labels are unchanged
    M1:
    EE can now only be reached from FF, giving the working value 6+19=256+19=25
    A1: working values for
    TT: 28 (via BB), 30 (via AA) and 25+2=2725+2=27 (via EE)
    A1: new shortest route
    S−F−E−TS-F-E-T of length 27 km
    B1: it is
    27−22=527-22=5 km longer than before
    R1: the new route uses the long road
    FEFE but is still shorter than the other routes to TT (28 and 30)

    Total for question 4: 12 marks

End of questions

Subtopic tests