Optimisation: Dijkstra's shortest path algorithm
This worksheet marks itself
Set it as homework or classwork and every answer is marked as pupils go, with feedback on what they got wrong. The scores go straight into your mark book, so you can see who needs help before the next lesson.
- 12 questions
- 34 marks
- about 35 minutes
- marked instantly
Question types: short answer, multiple choice, matching, true or false.
Try one from this worksheet
Identify the task that is a typical application of Dijkstra's shortest path algorithm.
Pick an answer: it's marked straight away, just as your pupils would see it.
About this resource
AQA A-level Computer Science (7517) 4.3.6.1 Dijkstra's shortest path algorithm: trace it, and know its applications. C# lesson 5 of 5 in 4.3 Fundamentals of algorithms: a trace-the-weighted-matrix Do Now, a short key idea, a 10-challenge ladder in three sets with exact test data, two exam questio…
17 slides.
Lesson outline
- Do Now: fewest edges or shortest?
- Do Now: answers
- Key idea: The shortest path on a weighted graph
- Key idea: Tracing it: one row per vertex visited
- Key idea: Reading the route back, and uses
- Key idea: Dijkstra in C#
- Set 1: the pieces
- Set 2: the whole algorithm
- Exam question E1: read the results
- Model answer E1
- Exam question E2: a satnav
- Model answer E2
