Dijkstra's Algorithm

This lesson covers Dijkstra's algorithm — a fundamental shortest-path algorithm for weighted graphs. It is a key topic in the OCR A-Level Computer Science (H446) specification, section 2.3.

---

The Shortest Path Problem

Given a weighted graph (where edges have numerical costs), the shortest path problem is to find the path between two vertices that minimises the total weight (sum of edge weights).

Why BFS is Not Enough

BFS finds the shortest path in unweighted graphs (fewest edges). But in weighted graphs, the path with fewest edges may not have the lowest total weight.

Example:

A --1-- B --1-- D     (A to D via B: total weight = 2)
A --10-- D            (A to D directly: total weight = 10)

BFS would find A -> D (1 edge), but the shortest weighted path is A -> B -> D (weight 2).

---

How Dijkstra's Algorithm Works

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights.

Key Idea