Topic study hub
Optimisation algorithms
Official AQA 7517 section 4.3.6.
0
Objectives
5
Flashcards
7
Questions
36 min
Study time
AqaA LevelComputer ScienceFundamentals of algorithms
Choose a revision tool
Start revising Optimisation algorithms
Syllabus checklist
What you need to know
0 objective pages available
Dijkstra’s shortest path algorithm1 objectives
- Dijkstra’s shortest path algorithm: Understand and be able to trace Dijkstra’s shortest path algorithm. Be aware of applications of shortest path algorithm. Students will not be expected to recall the steps in Dijkstra's shortest path algorithm.
Key terms
Weighted graphTentative distance
Exam tips
- Show route calculations: When tracing the algorithm, write the calculation for each possible improvement, such as 1 + 2 = 3.
Common mistakes
- Choosing the largest tentative distance: Select the unvisited vertex with the smallest tentative distance.
Practice preview
- A weighted graph has edges A-B = 4, A-C = 1, C-B = 2, B-D = 1 and C-D = 7. What is the shortest distance from A to D?
- In a trace of Dijkstra’s algorithm starting at vertex A, the current tentative distances are B = 4, C = 1 and D = infinity. Which vertex should be selected next?
- Which is an application of a shortest path algorithm?
Continue by objective
Objectives are grouped by subtopic so students can jump straight to the exact skill they want to revise.
Related topics