AQA 7517 · Paper 1 · 4.3.6

Dijkstra's
Algorithm

Shortest path in weighted graphs · Section 4.3 Algorithms

WHAT YOU'LL LEARN

Shortest path algorithm · Tentative distances · Priority queue · Step-by-step trace

AQA SPEC LINK

4.3.6 — Dijkstra's shortest path algorithm

Overview

What is Dijkstra's Algorithm?

Finds the shortest path from a source vertex to all other vertices in a weighted graph (non-negative weights only). Works by greedily visiting the closest unvisited node.

Used in: sat-nav routing, network packet routing, airline routes

Requires: non-negative edge weights (no negative weights)

Complexity: O((V + E) log V) with a priority queue

Algorithm Steps

Dijkstra's — Step by Step

1

Set distance to source = 0; all others = ∞

2

Add all vertices to an unvisited set

3

Pick unvisited vertex with smallest distance (priority queue)

4

For each neighbour: calculate new distance = current + edge weight. If smaller than stored distance, update it.

5

Mark current vertex as visited. Repeat from step 3 until all visited.

Example Graph

Dijkstra's Example Graph

Find shortest path from A to all nodes. Edges: A-B(4), A-C(2), B-D(5), C-B(1), C-D(8), B-E(6), D-E(2)

       A

      /  \

    4(B) 2(C)

     |    |

     ↓ 1→B 8(D)

     →D(5)→E(2)

Shorter: A→C→B(3) vs A→B(4)

Dijkstra Trace

Dijkstra's Trace Table

Visit	A	B	C	D	E
Start	0	∞	∞	∞	∞
Visit A	✓	4	2	∞	∞
Visit C(2)	✓	3	✓	10	∞
Visit B(3)	✓	✓	✓	8	9
Visit D(8)	✓	✓	✓	✓	9
Visit E(9)	✓	✓	✓	✓	✓

Shortest: A=0, B=3, C=2, D=8, E=9

Path Reconstruction

Reconstructing the Shortest Path

Store a previous node (predecessor) for each vertex when updating distances. Trace back from destination to source to recover the path.

Node	Shortest Dist	Previous Node
A	0	None
B	3	C
C	2	A
D	8	B
E	9	B

Path to E: E ← B ← C ← A → A → C → B → E (cost 9)

Complexity

Dijkstra's Complexity

Naive (array): O(V²) — scans all unvisited to find min

With priority queue (min-heap): O((V + E) log V) — more efficient

For dense graphs: array implementation may be simpler

Limitation: does NOT work with negative edge weights (use Bellman-Ford instead)

Applications

Real-World Applications

GPS/Sat-Nav — shortest route between two locations

Internet routing — OSPF protocol uses Dijkstra's to find fastest routes

Airline routes — cheapest/fastest path between airports

Games AI — pathfinding for game characters

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

A network has vertices P, Q, R, S with edges: P-Q(3), P-R(6), Q-R(2), Q-S(5), R-S(1).
(a) Using Dijkstra's algorithm, find the shortest path from P to S. Show all working. [5]
(b) State ONE limitation of Dijkstra's shortest path algorithm. [1]

[6 marks]

5 marks

(a) Init: P=0, Q=∞, R=∞, S=∞. Visit P: Q=3, R=6. Visit Q(3): R=min(6,3+2)=5, S=3+5=8. Visit R(5): S=min(8,5+1)=6. Visit S(6). Shortest: P→Q→R→S = 6

1 mark

(b) Does not work with negative edge weights

Summary

Key Points to Remember

Dijkstra's finds shortest path in weighted graphs with non-negative weights

Uses greedy approach — always visits closest unvisited node next

Tentative distances updated when shorter path found

Store previous node to reconstruct path

O((V+E) log V) with priority queue; O(V²) naive

🎉 Lesson complete — move to the quiz!