Date | November 2020 | Marks available | 6 | Reference code | 20N.3.AHL.TZ0.Hdm_2 |
Level | Additional Higher Level | Paper | Paper 3 | Time zone | Time zone 0 |
Command term | Find, Show, and Use | Question number | Hdm_2 | Adapted from | N/A |
Question
Christine and her friends live in Winnipeg, Canada. The weighted graph shows the location of their houses and the time, in minutes, to travel between each house.
Christine’s house is located at vertex .
Use Dijkstra’s algorithm to find the shortest time to travel from to , clearly showing how the algorithm has been applied.
Hence write down the shortest path from to .
A new road is constructed that allows Christine to travel from to in minutes. If Christine starts from home and uses this new road her minimum travel time to is reduced, but her minimum travel time to remains the same.
Find the possible values of .
Markscheme
attempts to construct a graph or table to represent Dijkstra’s algorithm M1
EITHER
OR
a clear attempt at Step 1 ( and considered) M1
Steps 2 and 3 correctly completed A1
Step 4 () correctly completed A1
Steps 5 and 6 ( and or or ) correctly completed A1
shortest time (mins) A1
[6 marks]
A1
Note: Award A1 only if it is clear that Dijkstra’s algorithm has been attempted in part (a) (i). This A1 can be awarded if the candidate attempts to use Dijkstra’s algorithm but neglects to state (mins).
[1 mark]
minimum travel time from to is reduced
is now (mins) (M1)
is still (mins)
so (A1)
Note: Condone .
travel time from to remains the same ( mins)
is now (mins) (M1)
(A1)
so A1
Note: Accept .
[5 marks]