Edexcel A-Level Further Maths
Dijkstra's algorithm
Total 27 marks
Name
Class
Date
- 1A road network joins a depot to a warehouse through four junctions , , and . The roads and their lengths in km are , , , , , , , and . Dijkstra's algorithm is used to find the shortest route from to .(a)What is the final label of vertex ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)Which is the shortest route from to and its length?[1 mark]- A, 19 km
- B, 18 km
- C, 18 km
- D, 17 km
Show the mark scheme
Mark scheme
Answer: D(c)Explain why the final label at is 6 and not 7.[2 marks]Show the mark scheme
Mark scheme
M1: after is labelled 4, the route gives
A1: 6 is less than the working value 7 from the direct road , so 7 is replaced by 6
Accept: the route via is shorter than the direct roadTotal for question 1: 4 marks
- 2Six towns to are joined by roads with lengths in km: , , , , , , , and . Dijkstra's algorithm is used starting from .(a)Counting as the first, which vertex receives the fourth permanent label?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(b)What is the final label of ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(c)Use the labels to find the shortest route from to and show how you worked it out.[2 marks]Show the mark scheme
Mark scheme
M1: working back from (20): (14) because , then (11) because , (7) because , (5) because
A1:
Accept: a trace back using the working values rather than the sumsTotal for question 2: 4 marks
- 3A courier network has seven vertices , , , , , and . The roads and their lengths in km are , , , , , , , , , and .(a)Apply Dijkstra's algorithm from . Show the working values at , and state the permanent labels of the next three vertices to be labelled after .[3 marks]
Show the mark scheme
Mark scheme
B1: labelled first with 8 (the smaller of and )
B1: has working values 12 then , so its label is 11
B1: labelled next with
Do not accept:(b)A courier must travel from to and must call at . Find the shortest such route and its length.[4 marks]Show the mark scheme
Mark scheme
M1: shortest route from to found by the algorithm: working values at are 19, 20 and 27
A1: of length 19 km
M1: add the shortest route from to , the road
A1: of length km
Accept: any correct working that shows the labels atTotal for question 3: 7 marks
- 4A delivery network has eight vertices , , , , , , and . The roads and their lengths in km are , , , , , , , , , , , and .(a)Use Dijkstra's algorithm to find the shortest route from to . 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 (0), working values and ; labelled first
A1: order of labelling , , , with labels 0, 3, 6, 12
A1: (via ), not 17 via
M1: has working values 25 (via ) then (via ), which replaces it
A1: then , , (working values for were 28 and 30)
A1: route , length 22 km
Accept: a trace back from using the labels(b)The road is closed. Explain why the labels of , , and do not change, find the new shortest route from to , and state how much longer it is.[6 marks]Show the mark scheme
Mark scheme
R1: , , and were all labelled before and their shortest routes do not use , so their labels are unchanged
M1: can now only be reached from , giving the working value
A1: working values for : 28 (via ), 30 (via ) and (via )
A1: new shortest route of length 27 km
B1: it is km longer than before
R1: the new route uses the long road but is still shorter than the other routes to (28 and 30)Total for question 4: 12 marks
End of questions