Dijkstra's Algorithm

Once edges carry weights — a road's length, a cable's latency, a flight's price — "shortest" stops meaning "fewest steps" and starts meaning "least total cost". Dijkstra's algorithm (Edsger Dijkstra, 1956) is the canonical answer to that problem: from a single source it computes the shortest-cost path to every other vertex in a weighted graph with non-negative weights. It is the algorithm humming inside every sat-nav, every routing protocol, and a huge fraction of game pathfinding, and it is the natural sequel to the breadth-first search you met in the graph-traversal lesson.

This lesson teaches you to run Dijkstra by hand — the skill OCR examines most heavily — through a fully traced worked example with a distance/previous table updated step by step. You will see why a priority queue turns a naive $V^2$V2 loop into something near-linear in the edges, where the algorithm's greedy correctness comes from, and exactly why a single negative edge breaks it. Dijkstra operates on a weighted graph; the graph data structure itself (adjacency lists vs matrices) is taught in the Graphs lesson of the OCR Data Structures course, which you should keep open alongside this one.

---

Spec Mapping

This lesson supports the OCR H446 section 2.3 content on standard algorithms, specifically Dijkstra's shortest-path algorithm, and connects to 1.4.2 (graphs as a data structure) and 1.3.x (network routing). Paraphrased, the assessable ideas are:

• Understanding the shortest-path problem on a weighted graph and why an unweighted traversal (BFS) does not solve it.
• Describing how Dijkstra's algorithm works as a greedy, single-source method that settles vertices in increasing order of distance.
• Tracing the algorithm on a given weighted graph, maintaining a distance table and a previous/back-pointer table, and reconstructing the actual path — not just its cost.
• Explaining the role of a priority queue and stating the time complexity under different implementations.
• Knowing the algorithm's limitations (non-negative weights, single source) and naming the right tool when they are violated.

As always we paraphrase; cross-check exact wording against the current OCR H446 specification.

---

The Shortest-Path Problem and Why BFS Is Not Enough

A weighted graph attaches a numerical cost to each edge. The shortest-path problem asks for the path between two vertices whose sum of edge weights is minimal. Breadth-first search finds the path with the fewest edges, which is the shortest path only when every edge costs the same. Once weights differ, the two notions diverge:

flowchart LR
    A((A)) -- "1" --- B((B))
    B -- "1" --- D((D))
    A -- "10" --- D

BFS reaches D in one hop (A→D) and declares that the answer. But A→B→D costs only $1+1=2$1+1=2, far cheaper than the direct edge of cost 10. BFS counts hops, Dijkstra counts cost — and that single change in objective is the whole reason a more careful algorithm is needed.

You might wonder whether we could "fix" BFS by simply repeating an edge of weight $w$w as $w$w separate unit-weight edges, then running ordinary BFS. In principle yes — but on a graph with weights in the thousands (road distances in metres, say) you would explode a handful of edges into millions of dummy vertices, turning a tiny problem into an intractable one. Dijkstra is, in effect, BFS made weight-aware without that blow-up: instead of expanding outward in rings of equal hop-count, it expands outward in rings of equal cost, always growing the frontier from its cheapest point. Holding that mental picture — a cost-ordered wavefront spreading from the source — makes every later step of the algorithm feel inevitable rather than arbitrary.

---

How Dijkstra's Algorithm Works

Dijkstra finds the shortest path from one source vertex to all others, provided every edge weight is non-negative.

Key idea: tentative distances that get "settled"

Maintain a distance table holding the best-known cost from the source to each vertex (the source starts at 0, everything else at infinity) and a previous table recording the predecessor on that best path (for reconstruction). The engine is greedy:

Repeatedly pick the unvisited vertex with the smallest tentative distance, mark it visited (its distance is now final), and relax each of its outgoing edges — i.e. check whether reaching a neighbour through this vertex beats the neighbour's current best.

The act of testing "is distance[current] + weight better than distance[neighbour]?" and updating if so is called edge relaxation, and it is the single operation at Dijkstra's heart. The word "relax" comes from physics: imagine each tentative distance as a stretched constraint that we loosen whenever we discover a shorter way round. A tentative distance is only ever an upper bound on the true distance — it can fall as better routes are found, but it never rises — and the moment we settle a vertex we promote that upper bound to a proven exact value. Keeping the two ideas distinct in your head (tentative-and-improvable versus settled-and-final) prevents almost every conceptual mistake students make with this algorithm.

Why the greedy choice is safe

When we pick the smallest-distance unvisited vertex u, can a cheaper route to u still appear later? No — any such route would have to pass through some other still-unvisited vertex w, but w's distance is ≥ u's (we chose the smallest), and edges are non-negative, so the detour through w cannot be cheaper. That argument is exactly why negative edges break Dijkstra: a later negative edge could undercut an already-"settled" distance, violating the invariant.

This is the intuition; the formal version, with the loop invariant stated explicitly and proved by induction, appears below in Why It Works. It is well worth understanding the reasoning rather than memorising the conclusion, because OCR's higher-mark questions increasingly ask candidates to justify algorithmic properties, not merely state them — and "Dijkstra is greedy and greed is safe here because the weights are non-negative" is a one-sentence answer that demonstrates genuine understanding.

Algorithm steps

1. Set distance[source] = 0; all other distances to infinity; all previous to null; all vertices unvisited.
2. While unvisited vertices remain: a. current = the unvisited vertex with the smallest tentative distance. b. For each unvisited neighbour n of current, compute newDist = distance[current] + weight(current, n). If newDist < distance[n], update distance[n] = newDist and previous[n] = current (relaxation). c. Mark current as visited — its distance is now final.

Pseudocode (OCR style)

# OCR-style pseudocode
procedure dijkstra(graph, source)
    for each vertex v in graph
        distance[v] = INFINITY
        previous[v] = null
        visited[v] = false
    next v
    distance[source] = 0

    while there are unvisited vertices
        current = unvisited vertex with smallest distance
        visited[current] = true

        for each unvisited neighbour n of current
            newDist = distance[current] + weight(current, n)
            if newDist < distance[n] then
                distance[n] = newDist
                previous[n] = current
            endif
        next n
    endwhile
endprocedure

Python implementation (priority-queue backed)

import heapq

def dijkstra(graph, source):
    distances = {v: float('inf') for v in graph}
    distances[source] = 0
    previous = {v: None for v in graph}
    visited = set()
    heap = [(0, source)]          # min-heap keyed on tentative distance

    while heap:
        current_dist, current = heapq.heappop(heap)
        if current in visited:    # stale entry — skip
            continue
        visited.add(current)

        for neighbour, weight in graph[current]:
            if neighbour not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[neighbour]:
                    distances[neighbour] = new_dist
                    previous[neighbour] = current
                    heapq.heappush(heap, (new_dist, neighbour))

    return distances, previous

The role of the priority queue

Step (a) — "find the unvisited vertex with the smallest distance" — is the bottleneck. Scanning every vertex each time costs $O(V)$O(V) per selection, giving $O(V^2)$O(V2) overall. A priority queue (a min-heap; see the Priority queues / heaps material in the Data Structures course) returns the minimum in $O(\log V)$O(logV) and lets us push updated distances as we relax edges. Because we may push several entries for the same vertex, we guard with a "skip if already visited" check rather than deleting old entries — a standard implementation trick.

---

Worked Example (Fully Traced)

Consider this weighted graph:

flowchart LR
    A((A)) -- "4" --- B((B))
    A -- "2" --- C((C))
    B -- "1" --- D((D))
    B -- "7" --- E((E))
    C -- "3" --- D
    D -- "5" --- E

Adjacency list:

Vertex	Adjacency list (neighbour, weight)
A	(B, 4), (C, 2)
B	(A, 4), (D, 1), (E, 7)
C	(A, 2), (D, 3)
D	(B, 1), (C, 3), (E, 5)
E	(B, 7), (D, 5)

We find shortest paths from A. The combined distance/previous table after each vertex is settled:

Step	Settled (current)	A	B (prev)	C (prev)	D (prev)	E (prev)	Visited set
Init	—	0	∞ (–)	∞ (–)	∞ (–)	∞ (–)	{}
1	A (dist 0)	0	4 (A)	2 (A)	∞ (–)	∞ (–)	{A}
2	C (dist 2)	0	4 (A)	2 (A)	5 (C)	∞ (–)	{A, C}
3	B (dist 4)	0	4 (A)	2 (A)	5 (C)	11 (B)	{A, B, C}
4	D (dist 5)	0	4 (A)	2 (A)	5 (C)	10 (D)	{A, B, C, D}
5	E (dist 10)	0	4 (A)	2 (A)	5 (C)	10 (D)	all

Relaxations, step by step

Step 1 — settle A (distance 0). Relax A's edges:

• B: $0 + 4 = 4 < \infty$0+4=4<∞ → set distance[B]=4, previous[B]=A.
• C: $0 + 2 = 2 < \infty$0+2=2<∞ → set distance[C]=2, previous[C]=A.

Step 2 — settle C (smallest unvisited = 2). Relax C's edges:

• D: $2 + 3 = 5 < \infty$2+3=5<∞ → set distance[D]=5, previous[D]=C. (A already visited.)

Step 3 — settle B (smallest unvisited = 4). Relax B's edges:

• D: $4 + 1 = 5$4+1=5, not $< 5$<5 → no change. (Ties do not update; D's predecessor stays C.)
• E: $4 + 7 = 11 < \infty$4+7=11<∞ → set distance[E]=11, previous[E]=B.

Step 4 — settle D (smallest unvisited = 5). Relax D's edges:

• E: $5 + 5 = 10 < 11$5+5=10<11 → set distance[E]=10, previous[E]=D (overwrites the earlier prev).

Step 5 — settle E (distance 10). No unvisited neighbours; algorithm ends.

Reconstructing the paths from previous

Follow back-pointers from each target to the source and reverse:

Vertex	Shortest distance	Back-pointer chain	Path
A	0	A	A
B	4	B←A	A → B
C	2	C←A	A → C
D	5	D←C←A	A → C → D
E	10	E←D←C←A	A → C → D → E

Notice E's path goes via C and D even though there is a direct B→E edge: the cost (10) beats the alternative A→B→E ($4+7=11$4+7=11). Reading the previous column is the part students most often skip, yet "state the path, not just the cost" is where the final marks live.

Tracing Dijkstra under exam conditions

Trace questions are where Dijkstra marks are won and lost, and they reward method as much as the final figures. A reliable routine:

1. Draw the table first, with one row per "settle" step and one column per vertex. Add a column for the visited set and, ideally, write each cell as distance (previous) so the back-pointers are baked in from the start rather than reconstructed in a panic at the end.
2. Initialise honestly: source = 0, everything else = ∞, all predecessors blank. A surprising number of lost marks trace back to a mis-initialised first row.
3. At each step, underline or circle the chosen vertex — the unvisited one with the smallest tentative distance. State the tie-break rule you are using (alphabetical, say) and apply it consistently; examiners accept any consistent rule.
4. Show the relaxation arithmetic, even briefly: "via C, D = 2 + 3 = 5". This is the working that earns method marks if your final number slips.
5. Never touch a settled vertex again. Once a vertex is circled it is frozen; only its unvisited neighbours are updated.
6. Finish by reconstructing the path from the predecessor chain and quoting both the route and its cost.

A common worry is what to do when two unvisited vertices share the smallest distance. The reassuring answer: it does not matter which you settle first — the final distances are identical either way — but you must pick one, settle it fully, and move on. Inventing a "joint settle" or skipping the tie corrupts the trace.

It is also worth internalising what the table is telling you at the moment the algorithm stops. Every figure in the final row is a guaranteed shortest distance, and the predecessor chain encodes a single shortest-path tree rooted at the source: a tree because each vertex has exactly one predecessor, and "shortest-path" because every root-to-vertex walk in it is optimal. That one structure simultaneously answers "how far?" and "by which route?" for every destination — the economy that makes Dijkstra so powerful in routing.

---

Time Complexity

Implementation	Selecting the minimum	Overall
Simple array / linear scan	$O(V)$O(V) per step	$O(V^2)$O(V2)
Binary heap (priority queue)	$O(\log V)$O(logV) per op	$O((V + E)\,\log V)$O((V+E)logV)
Fibonacci heap	amortised $O(1)$O(1) decrease-key	$O(V \log V + E)$O(VlogV+E)

For dense graphs ($E \approx V^2$E≈V2) the simple $O(V^2)$O(V2) array is actually competitive; for sparse graphs the binary-heap version wins. For the OCR exam, being able to quote $O(V^2)$O(V2) for a basic implementation and $O((V + E)\,\log V)$O((V+E)logV) with a priority queue is sufficient.