Mastering Dijkstra's Shortest Path Algorithm for A-Level Computer Science

Introduction to Dijkstra's Algorithm

In the world of A-Level Computer Science, understanding how to navigate weighted graphs is a fundamental skill. Dijkstra's algorithm, developed by Edsger W. Dijkstra in 1956, is the gold standard for finding the shortest path from a single source node to all other nodes in a graph with non-negative edge weights. Whether you are modelling network traffic, GPS navigation, or social network connections, this algorithm provides an efficient, systematic approach to solving complex routing problems.

For your exams, you are not just expected to know the theory; you must be able to perform the algorithm manually on a given graph. This article will break down the mechanics of the algorithm, provide clear worked examples, and highlight the common mistakes that often cost students marks. By the end, you will have a robust understanding of how to apply this greedy algorithm with confidence.

Understanding Weighted Graphs and Path Costs

Before diving into the algorithm, we must define our terms. A weighted graph consists of nodes (vertices) connected by edges, where each edge has an associated numerical value called a weight. This weight can represent distance, time, cost, or any other metric. The length of a path is the sum of the weights of all edges along that path.

If we have a path $p$ consisting of edges $e_1, e_2, ..., e_n$, the total cost $C(p)$ is calculated as:

$$C(p) = \sum_{i=1}^{n} w(e_i)$$

Dijkstra's algorithm is a greedy algorithm, meaning it makes the locally optimal choice at each stage with the hope of finding the global optimum. It maintains a set of 'visited' nodes and a set of 'unvisited' nodes, iteratively updating the shortest known distance from the source to every other node.

The Step-by-Step Process

To perform Dijkstra's algorithm manually, follow these steps consistently:

1. Initialisation: Assign a distance value of $0$ to the source node and $\infty$ to all other nodes. Mark all nodes as unvisited.
2. Selection: From the set of unvisited nodes, select the node with the smallest current distance. This becomes your 'current' node.
3. Relaxation: For the current node, consider all its unvisited neighbours. Calculate their tentative distance from the source: $new_distance = current_node_distance + edge_weight$. If this value is less than the previously recorded distance, update it.
4. Finalisation: Once all neighbours of the current node have been considered, mark the current node as visited. A visited node is never checked again.
5. Iteration: Repeat steps 2 to 4 until all nodes are visited or the target node is reached.

Worked Example 1: Simple Network

Consider a graph with nodes A, B, C, and D. We want the shortest path from A to D.

• A to B (weight 4)
• A to C (weight 2)
• B to C (weight 1)
• B to D (weight 5)
• C to D (weight 8)

Step 1: Start at A. Distances: A=0, B=$\infty$, C=$\infty$, D=$\infty$. Step 2: Current is A. Neighbours B (0+4=4) and C (0+2=2). Update: B=4, C=2. Mark A visited. Step 3: Smallest unvisited is C (dist 2). Neighbours of C: B (2+1=3) and D (2+8=10). Update: B=3 (since 3 < 4), D=10. Mark C visited. Step 4: Smallest unvisited is B (dist 3). Neighbours of B: D (3+5=8). Update: D=8 (since 8 < 10). Mark B visited. Step 5: Smallest unvisited is D (dist 8). Mark D visited. The shortest path to D is 8.

Worked Example 2: Complex Routing

Imagine a graph where we need to find the shortest path from node S to node T.

• S to A (3), S to B (2)
• A to C (4), A to D (1)
• B to A (1), B to D (7)
• C to T (2)
• D to T (5)

Iteration 1: Start S=0. Neighbours A=3, B=2. Visited: {S}. Iteration 2: Current B (dist 2). Neighbours A (2+1=3, no change), D (2+7=9). Visited: {S, B}. Iteration 3: Current A (dist 3). Neighbours C (3+4=7), D (3+1=4). Update D=4. Visited: {S, B, A}. Iteration 4: Current D (dist 4). Neighbours T (4+5=9). Update T=9. Visited: {S, B, A, D}. Iteration 5: Current C (dist 7). Neighbours T (7+2=9, no change). Visited: {S, B, A, D, C}. Final: Shortest distance to T is 9.

Common Mistakes

1. Forgetting to update: Students often forget to update a node's distance if they find a shorter path later in the process. Always check if the new path is strictly smaller than the current value.
2. Incorrect selection: Always pick the unvisited node with the smallest distance. Picking the wrong node will lead to an incorrect final result.
3. Ignoring visited nodes: Once a node is marked as visited, its distance is final. Do not attempt to 're-visit' or update it, as this violates the algorithm's logic.
4. Negative weights: Dijkstra's algorithm fails if the graph contains negative edge weights. While not common in basic A-Level questions, remember that it is designed specifically for non-negative weights.

Frequently Asked Questions

Does Dijkstra's algorithm work on unweighted graphs? Yes, but it is overkill. For unweighted graphs, Breadth-First Search (BFS) is more efficient.

What is the time complexity of Dijkstra's? Using a simple array, it is $O(V^2)$. Using a priority queue (min-heap), it can be optimised to $O((V+E) \log V)$, where $V$ is vertices and $E$ is edges.

Why is it called a 'greedy' algorithm? It is greedy because it always chooses the closest unvisited node, assuming that this local choice will lead to the global shortest path.

Can Dijkstra's find the path between any two nodes? Yes, by running the algorithm until the target node is marked as visited, you can determine the shortest path from the source to that specific target.

Conclusion

Dijkstra's algorithm is a cornerstone of computer science, providing a reliable method for pathfinding in weighted graphs. By practising the steps of initialisation, selection, and relaxation, you can ensure you pick up full marks in your A-Level exams. Remember to stay methodical and always double-check your arithmetic during the relaxation phase.

Ready to see this in action? Head over to MathInstructor AI to generate a free, narrated animated lesson that visualises Dijkstra's algorithm step-by-step, making these abstract concepts crystal clear.