Dijkstra’s shortest path algorithm — AQA A-Level Computer Science
Dijkstra's algorithm is a greedy graph traversal algorithm designed to find the shortest path between a starting node and all other nodes in a weighted graph with non-negative edge weights. In AQA A-Level Computer Science, it demonstrates how priority queues and graph theory are combined to solve real-world routing and network optimisation problems efficiently.
Dijkstra’s shortest path algorithm explained
Dijkstra's shortest path algorithm finds the minimum-cost route from a single source vertex to every other vertex in a weighted graph with non-negative edge weights.
Read the full explanation
To trace it, maintain a table recording, for each vertex, its current shortest known distance from the source and its predecessor. Initially the source has distance 0 and all others have infinity. At each step, select the unvisited vertex with the smallest current distance, mark it as visited, and examine each of its unvisited neighbours. For each neighbour, calculate the distance through the selected vertex (its distance plus the edge weight); if this is smaller than the neighbour's recorded distance, update the distance and set the predecessor to the selected vertex. Repeat until all vertices are visited.
Your focus
- Understand and be able to trace Dijkstra’s shortest path algorithm.
Which command word is this?
Follow the execution of the algorithm step-by-step, recording all state changes, updated tentative distances, visited statuses, and predecessor pointers in the provided table.
Dijkstra’s shortest path algorithm exam tips
Topic Overview
Dijkstra's algorithm is a fundamental graph theory algorithm covered in Section 4.4 (Data structures) and Section 4.5 (Algorithms) of the AQA A-Level Computer Science syllabus. It operates as a greedy search algorithm that computes the single-source shortest path tree for a directed or undirected graph with non-negative edge weights.
Mastering this algorithm is essential because it demonstrates the application of abstract data types such as priority queues, adjacency matrices, and adjacency lists to solve computational problems. It provides the foundation for networking protocols (such as OSPF) and mapping navigation software encountered throughout computer systems.
Key Concepts
- →Greedy strategy: The algorithm always selects the unvisited node with the smallest tentative distance, assuming this local optimum leads to the global shortest path.
- →Edge relaxation: The process of testing whether reaching an adjacent node v through the current node u reduces v's known tentative distance, updating dist[v] = dist[u] + weight(u, v).
- →Predecessor tracking: Maintaining a record of the preceding node on the optimal path so the complete route can be reconstructed via reverse traversal once the target is reached.
- →Data structure dependence: Performance varies directly with the underlying data structure; priority queues (min-heaps) optimise dense extraction steps compared to sequential arrays.
Marking Points
- Initialises the source distance to 0 and all other distances to infinity before processing begins
- Selects the unvisited vertex with the smallest current distance at each step
- Updates a neighbour's distance and predecessor only when the route through the selected vertex is shorter
- Records the state of the distance and predecessor table after each iteration to show the trace
- Reconstructs the shortest path to a target by following predecessors back to the source
Examiner Tips
- 💡Draw a table with a column for each vertex's distance and predecessor, and update it row by row
- 💡Show the order in which vertices are visited so your trace can be checked
- 💡Check that each recorded distance equals the sum of edge weights along the stored predecessor route
- 💡When completing trace tables in Paper 1, cross out superseded tentative values cleanly with a single line rather than scribbling over them, ensuring markers can follow your steps.
- 💡Always state both the path sequence (e.g., A -> C -> B) and the final numerical cost when an exam question requests the shortest path.
- 💡Be ready to compare Dijkstra's against Breadth-First Search (BFS); highlight that BFS only finds shortest paths in unweighted graphs, whereas Dijkstra's handles weighted edges.
Common Mistakes
- Updates a neighbour's distance even when the new route is longer; correct by comparing the new total with the existing recorded distance first
- Selects vertices in arbitrary order rather than the smallest current distance; correct by always choosing the minimum unvisited distance
- Forgets to set or update the predecessor when a distance changes; correct by recording the vertex that produced the shorter route
- Assuming Dijkstra's algorithm works with negative edge weights: Students often forget that Dijkstra's greedily marks nodes as finalised; negative edges can subsequently invalidate finalised paths.
- Confusing Dijkstra's algorithm with the A* search algorithm: Dijkstra's evaluates paths purely on path cost accumulated from the start node (g(x)), whereas A* incorporates a heuristic estimate to the goal (h(x)).
- Believing visited nodes can be re-evaluated: In standard Dijkstra's with non-negative weights, once a node is marked visited/finalised, its shortest distance is permanent and never updated again.
Revision Plan
- 1Day 1-2: Review graph representations and manually trace Dijkstra's algorithm on small 4-6 node graphs using pen, paper, and trace tables.
- 2Day 3-4: Implement Dijkstra's algorithm in your NEA programming language (Python, C#, or Java) using an adjacency list and a priority queue.
- 3Day 5-6: Compare Dijkstra's time complexity across array vs min-heap implementations and practice past-paper exam questions detailing limitations with negative weights.
- 4Day 7: Contrast Dijkstra's with A* heuristic search and Breadth-First Search to consolidate classification and command-word comparison questions.
Exam Question Types
- 📋Trace table questions: Given a weighted graph diagram, complete a table showing current node, unvisited set, tentative distances, and predecessor nodes step-by-step.
- 📋Algorithm adaptation / pseudocode: Write or complete structured pseudocode implementing Dijkstra's algorithm using standard queue/array operations.
- 📋Evaluation and comparison: Discuss the appropriateness of Dijkstra's versus A* or BFS for a given real-world scenario (e.g., sat-nav routing vs maze solving).
Command Word Expectations (AQA)
Follow the execution of the algorithm step-by-step, recording all state changes, updated tentative distances, visited statuses, and predecessor pointers in the provided table.
Provide a clear, reasoned account of why a mechanism operates in a certain way (e.g., why negative weights cause failure or why priority queues reduce complexity), using precise technical vocabulary.
Identify both similarities and differences between two algorithms (such as Dijkstra and A*), addressing algorithmic strategy, time complexity, and suitability for specific scenarios.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: Consider an undirected weighted graph with nodes A, B, C, D, and E. Edge weights are: A-B (4), A-C (2), B-C (1), B-D (5), C-D (8), C-E (10), D-E (2). Trace Dijkstra's algorithm starting at node A to determine the shortest path and total distance from A to E. Show the order of node visits and final distances.
- 1.Step 1: Initialise distances: dist[A]=0, dist[B]=infinity, dist[C]=infinity, dist[D]=infinity, dist[E]=infinity. All nodes are unvisited. Previous node pointers are undefined.
- 2.Step 2: Visit node A (current shortest distance = 0). Update neighbours: dist[B] = min(infinity, 0 + 4) = 4 (prev: A); dist[C] = min(infinity, 0 + 2) = 2 (prev: A). Mark A as visited.
- 3.Step 3: Select unvisited node with minimum distance: Node C (dist=2). Update unvisited neighbours: dist[B] = min(4, 2 + 1) = 3 (prev: C); dist[D] = min(infinity, 2 + 8) = 10 (prev: C); dist[E] = min(infinity, 2 + 10) = 12 (prev: C). Mark C as visited.
- 4.Step 4: Select unvisited node with minimum distance: Node B (dist=3). Update unvisited neighbours: dist[D] = min(10, 3 + 5) = 8 (prev: B). Mark B as visited.
- 5.Step 5: Select unvisited node with minimum distance: Node D (dist=8). Update unvisited neighbours: dist[E] = min(12, 8 + 2) = 10 (prev: D). Mark D as visited.
- 6.Step 6: Select unvisited node with minimum distance: Node E (dist=10). All reachable nodes visited. Backtrack from E: E -> D (prev D) -> B (prev B) -> C (prev C) -> A (prev A).
Question: Explain the time complexity of Dijkstra's algorithm when implemented using: (i) an adjacency matrix and an unindexed array, and (ii) an adjacency list with a min-heap priority queue. State which implementation is preferred for sparse graphs and justify your answer.
- 1.Step 1: For an array and adjacency matrix implementation, finding the minimum unvisited node takes O(V) time per iteration across V vertices, giving O(V^2). Updating distances takes O(V) per vertex, yielding an overall time complexity of O(V^2).
- 2.Step 2: For a min-heap and adjacency list implementation, extracting the minimum vertex takes O(log V) time (repeated V times: O(V log V)). Each edge relaxation takes O(log V) time using a decrease-key operation across all E edges (O(E log V)). This gives an overall time complexity of O((V + E) log V).
- 3.Step 3: Compare for sparse graphs where E is much less than V^2 (approximately E proportional to V). O((V + E) log V) simplifies to O(V log V), which is significantly faster than O(V^2).