Dijkstra's algorithm finds the shortest path between nodes in a weighted graph — one where each edge has a numerical cost. Starting from a source node, it repeatedly selects the unvisited node with the lowest known distance and updates neighbouring nodes' distances. For GCSE Computer Science, you need to trace this process step by step through a table.

What problem does Dijkstra's algorithm solve?

Imagine a network of towns connected by roads, where each road has a distance in kilometres. You want to travel from town A to town F using the shortest total distance — not the fewest roads. Dijkstra's algorithm answers this question efficiently for any weighted graph where edge costs are non-negative.

Real-world uses include:

  • GPS navigation — finding the fastest route between two locations
  • Internet routing — routers use similar algorithms (OSPF) to find efficient paths for data packets
  • Games — finding a character's shortest path through a game world

What does the algorithm need to run?

Before you begin Dijkstra's algorithm, you need:

  1. A weighted graph — nodes (vertices) connected by edges, each edge labelled with a non-negative numerical weight.
  2. A source node — the starting point.
  3. A distance table — initialised to infinity (∞) for every node except the source, which starts at 0.
  4. A visited set — initially empty. Once a node is visited, its shortest distance is finalised.

How do you apply Dijkstra's algorithm? A worked example

Consider this weighted graph with five nodes (A, B, C, D, E) and the following connections:

  • A → B: 4
  • A → C: 2
  • B → D: 3
  • B → E: 6
  • C → B: 1
  • C → D: 8
  • D → E: 2

Find the shortest path from A to every other node.

Step 1: Initialise the distance table.

Node Shortest distance from A Previous node Visited?
A 0 — No
B ∞ — No
C ∞ — No
D ∞ — No
E ∞ — No

Step 2: Visit A (distance 0). Update neighbours.

  • A → B: 0 + 4 = 4 (update B to 4, prev = A)
  • A → C: 0 + 2 = 2 (update C to 2, prev = A)

Mark A as visited.

Node Distance Previous Visited?
A 0 — ✓
B 4 A No
C 2 A No
D ∞ — No
E ∞ — No

Step 3: Visit the unvisited node with the lowest distance → C (distance 2). Update neighbours.

  • C → B: 2 + 1 = 3 (3 < 4, so update B to 3, prev = C)
  • C → D: 2 + 8 = 10 (update D to 10, prev = C)

Mark C as visited.

Node Distance Previous Visited?
A 0 — ✓
B 3 C No
C 2 — ✓
D 10 C No
E ∞ — No

Step 4: Visit B (distance 3). Update neighbours.

  • B → D: 3 + 3 = 6 (6 < 10, update D to 6, prev = B)
  • B → E: 3 + 6 = 9 (update E to 9, prev = B)

Mark B as visited.

Node Distance Previous Visited?
A 0 — ✓
B 3 C ✓
C 2 — ✓
D 6 B No
E 9 B No

Step 5: Visit D (distance 6). Update neighbours.

  • D → E: 6 + 2 = 8 (8 < 9, update E to 8, prev = D)

Mark D as visited.

Step 6: Visit E (distance 8). No unvisited neighbours. Mark as visited. Algorithm complete.

Final shortest distances from A:

Destination Shortest distance Path
B 3 A → C → B
C 2 A → C
D 6 A → C → B → D
E 8 A → C → B → D → E

How do you read off the shortest path?

To reconstruct the path from A to E, follow the "Previous node" column backwards:

  • E's previous = D
  • D's previous = B
  • B's previous = C
  • C's previous = A (source)

Reading forwards: A → C → B → D → E, total distance 8.

What is the time complexity of Dijkstra's algorithm?

With a simple implementation (scanning all nodes each step), the algorithm runs in O(V²) time, where V is the number of nodes. With a priority queue (a data structure that efficiently finds the minimum), it improves to O((V + E) log V), where E is the number of edges. For GCSE, you are expected to trace the algorithm rather than analyse its complexity formally, but understanding that it is efficient for typical graph sizes is good exam context.

When does Dijkstra's algorithm fail?

Dijkstra's algorithm requires that all edge weights are non-negative. If a graph contains a negative-weight edge, the algorithm can produce incorrect results because it assumes that once a node is visited (its distance finalised), no shorter path can be found via a later node. The Bellman-Ford algorithm handles negative weights correctly, but this is beyond GCSE scope.

Frequently asked questions

Do I need to memorise Dijkstra's algorithm for the GCSE exam?

For AQA GCSE Computer Science, you need to be able to trace through Dijkstra's algorithm given a weighted graph, completing a table showing the shortest distances and previous nodes at each step. You are not expected to write it in code at GCSE, but understanding the logic well enough to predict the next step in a partially completed trace is essential.

What happens if two unvisited nodes have the same distance?

If two unvisited nodes share the lowest current distance, either can be selected next — the algorithm remains correct regardless of which you choose. In an exam, the question may specify a tiebreaker rule (for example, choose alphabetically), or may accept either order. Always check the question wording.

Breadth-first search (BFS) finds the path with the fewest edges (hops) but ignores edge weights — every edge is treated as having a cost of 1. Dijkstra's algorithm finds the path with the lowest total weight, taking edge costs into account. For an unweighted graph, or a graph where all edges have equal weight, BFS gives the same result as Dijkstra's and runs faster.

Why is the starting node's distance set to 0 and all others to infinity?

Setting the starting node to 0 reflects that the cost of reaching it from itself is nothing. Setting all others to ∞ (infinity) is a programming convention meaning "not yet reachable" — any real path cost will be smaller than ∞, so the first valid path found will immediately update the distance. In code, ∞ is often represented as float('inf') in Python or a very large integer such as 999999.

Trace Dijkstra's algorithm through your own graphs with step-by-step hints from Professor Turing at aitutors.me.