User interface language: English | Español

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 C.

Use Dijkstra’s algorithm to find the shortest time to travel from C to F, clearly showing how the algorithm has been applied.

[6]
a.i.

Hence write down the shortest path from C to F.

[1]
a.ii.

A new road is constructed that allows Christine to travel from H to A in t minutes. If Christine starts from home and uses this new road her minimum travel time to A is reduced, but her minimum travel time to F remains the same.

Find the possible values of t.

[5]
b.

Markscheme

attempts to construct a graph or table to represent Dijkstra’s algorithm       M1

EITHER

OR

a clear attempt at Step 1 (C, D, H and B considered)        M1

Steps 2 and 3 correctly completed        A1

Step 4 (A :4436) correctly completed        A1

Steps 5 and 6 (E :4140  and  F :5857  or  5755  or  5855) correctly completed        A1

shortest time =55  (mins)        A1


[6 marks]

a.i.

CHGEF        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 55 (mins).


[1 mark]

a.ii.

minimum travel time from C to A is reduced

CHA is now 12+t  (mins)        (M1)

CBA is still 25+11  (mins)

so 12+t<36  t<24        (A1)


Note: Condone t24.


travel time from C to F remains the same (55 mins)

CHAF is now 12+t+21  (mins)        (M1)

12+t+2155  t22        (A1)

so 22t<24         A1


Note: Accept t=22, 23.


[5 marks]

b.

Examiners report

[N/A]
a.i.
[N/A]
a.ii.
[N/A]
b.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman
Show 87 related questions
Topic 3—Geometry and trigonometry

View options