AQA 7517 4.3.6.1: Dijkstra's shortest path algorithm
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
In module A4 you met weighted graphs and breadth-first search. Breadth-first search finds the route with the fewest edges, which is only the shortest route when every edge costs the same. On the mat the roads between zones have different lengths, so the robot needs the route with the smallest total weight. Dijkstra's algorithm finds it.
- The algorithm
- A trace
- Why it works, and when it does not
- In Python
- Efficiency
- Where it is used
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A5.7 Dijkstra's shortest path algorithm Algorithms and complexity
Tracing Dijkstra's algorithm in a table, why negative weights break it, a priority queue version, its efficiency and applications. - A5.9 Project: plan the route, then drive it Algorithms and complexity
Choose and justify a route planner, build the mat's graph, find the shortest route with Dijkstra's algorithm and drive it.
Try it on a robot
The task from A5.7 Dijkstra's shortest path algorithm, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.3.6.1 and is not endorsed by the board.