Dijkstra's Shortest Path Algorithm

AQA 4.3.6 — Dijkstra's algorithm

Retrieval: BFS (this sequence) finds the shortest path by fewest edges in an unweighted graph. Sequence 12's representing-graphs lesson introduced weighted graphs, where an edge carries a genuine cost. Dijkstra's algorithm extends BFS's shortest-path idea to weighted graphs — finding the path with the smallest total cost, not merely the fewest hops.

Key vocabulary

• Tentative distance — the shortest distance found so far to a vertex; may still improve as the algorithm continues.
• Finalised / visited vertex — a vertex whose shortest distance is now guaranteed correct and will never change again.
• Relaxation — updating a neighbour's tentative distance if a shorter path through the current vertex has just been found.
• Greedy algorithm — one that always makes the locally best choice at each step, without reconsidering it later.

Understand — the greedy strategy

Starting from a source vertex (distance 0, every other vertex initially "infinity"), Dijkstra repeatedly: picks the unvisited vertex with the smallest tentative distance, finalises it, then relaxes every neighbour — updating their tentative distance if reaching them via the just-finalised vertex is shorter than what's currently recorded.

See it — implementation

def dijkstra(graph, start):
    distances = {v: float("inf") for v in graph}
    distances[start] = 0
    unvisited = set(graph.keys())
    while unvisited:
        current = min(unvisited, key=lambda v: distances[v])
        if distances[current] == float("inf"):
            break
        unvisited.remove(current)
        for neighbour, weight in graph[current]:
            new_distance = distances[current] + weight
            if new_distance < distances[neighbour]:
                distances[neighbour] = new_distance
    return distances

Trace it — a small weighted graph

Edges: A–B (4), A–C (1), C–B (2), B–D (5), C–D (8). Starting from A:

Shortest distance from A to D: 8 — via A→C→B→D (1+2+5), genuinely shorter than the direct-ish A→C→D route (1+8=9), which relaxation correctly discovers and overwrites.

Reason about correctness — why the greedy choice is valid

When a vertex is chosen as having the smallest tentative distance among all unvisited vertices, that distance can never improve later. Any alternative path to it would have to pass through another currently unvisited vertex — which, by definition of the selection just made, has a tentative distance greater than or equal to the chosen vertex's. Since every edge weight is non-negative, extending that longer-or-equal path with one more edge can only make it longer still, never shorter than the vertex already chosen. This is exactly why finalising the minimum-distance vertex at each step is always safe.

Reason about correctness — why Dijkstra relies on non-negative edge weights

The greedy argument above depends entirely on "adding a non-negative edge weight can only increase or maintain a path's length." If a negative edge weight existed, that guarantee breaks: a vertex finalised early (with what seemed like the shortest distance) could later be reached more cheaply via a path that goes through a distant negative edge — but Dijkstra never revisits a finalised vertex, so it would never discover that shorter path. Concretely: with edges A→B (5), A→C (2), C→B (−4), the true shortest A→B distance is 2 + (−4) = −2 via C, but Dijkstra finalises B at distance 5 before ever exploring C's negative edge back to B, and never corrects it.

Debug it — diagnose, explain, fix, test, justify (wrong shortest-path assumption)

def dijkstra_stop_early(graph, start, target):
    distances = {v: float("inf") for v in graph}
    distances[start] = 0
    unvisited = set(graph.keys())
    while unvisited:
        current = min(unvisited, key=lambda v: distances[v])
        unvisited.remove(current)
        for neighbour, weight in graph[current]:
            new_distance = distances[current] + weight
            if new_distance < distances[neighbour]:
                distances[neighbour] = new_distance
                if neighbour == target:
                    return new_distance    # returns the instant a path to target is FOUND
    return distances[target]

On the graph A–B (4), A–C (1), C–B (2), B–D (5), C–D (8), calling dijkstra_stop_early(graph, "A", "D") returns 9 — a perfectly plausible-looking distance. The full trace above proves the genuine shortest distance is 8.

1. Diagnose: at the moment this function returns, has D been reached via every vertex that could possibly offer a shorter route, or only some of them?
2. Explain: compare against the full trace — which vertex, finalised after D is first relaxed here, is responsible for updating D's distance down from 9 to 8 in the correct version?
3. Fix: propose a correct fix.
4. Test: confirm the fixed version returns exactly 8, matching the full trace.
5. Justify: explain the genuine difference between a vertex being reached for the first time and a vertex having its shortest distance finalised, and why this bug confuses the two.

(At the point of the early return, D has only been relaxed via C (distance 1+8=9) - B has not yet been finalised, so the shorter route through B (distance 3+5=8) has never been considered. The bug returns the instant ANY path to the target is discovered, not once the target's distance is actually guaranteed shortest (which the correctness argument above shows only holds once a vertex is properly SELECTED as the current minimum, not merely relaxed). The fix removes the early return from inside the relaxation loop entirely, letting the main loop's proper minimum-selection process reach D naturally, exactly as the working version does. This is dangerous precisely because 9 is a completely plausible distance for this graph - nothing about the number itself signals that a shorter route exists.)

Common mistake

Assuming Dijkstra always needs to compute shortest distances to every vertex, even when only one target matters. Stopping early is a legitimate optimisation — but only once the target vertex has actually been selected as the current minimum (finalised), never merely "the first time it's mentioned" in a neighbour relaxation.

Analyse — complexity

This simple, array-based version is O(V²): the outer loop runs V times (once per vertex), and each iteration scans all unvisited vertices — up to V of them — to find the minimum, an O(V) operation repeated V times. Relaxing every edge across the whole run adds O(E). For a graph where E is much smaller than V² (a sparse graph), this V² term dominates — which is precisely why real-world implementations typically use a priority queue instead of a plain linear scan, reducing the complexity to O((V + E) log V). This course doesn't require implementing that improvement, but understanding why it matters — the same sparse-graph reasoning from Sequence 12's representation choice — is part of genuinely understanding the algorithm's performance.

Compare, select, justify

A delivery app needs the shortest route between two depots in a weighted road network (journey times vary by road). Explain why BFS would not be sufficient here, and why Dijkstra is necessary.

(BFS finds the path with the FEWEST edges, treating every edge as equally costly - it has no concept of one road taking longer than another. A route with fewer roads but much longer journey times could be genuinely worse than a route with more, shorter roads, and BFS cannot distinguish between them at all. Dijkstra is necessary because it correctly accounts for each edge's actual weight (journey time) when determining the truly shortest route.)

Synoptic application — combining representation, algorithm and performance

A national delivery company's route-planning system currently models around 200 depots as a weighted graph, using an adjacency list (Sequence 12), and computes shortest routes using the simple O(V²) Dijkstra implementation above. The company is expanding to 50,000 depots across the country, with each depot still only directly connected to a handful of nearby depots (the graph remains genuinely sparse).

Address all three of the following in your answer:

1. Data structure: is an adjacency list still the appropriate representation at 50,000 depots? Justify your answer with reference to Sequence 12's sparse-graph reasoning.
2. Algorithm: is Dijkstra still the appropriate algorithm choice, or would BFS ever be appropriate here? Justify your answer.
3. Performance: explain what happens to the O(V²) implementation's practical performance as V grows from 200 to 50,000, and what change (referenced but not implemented in this course) would address it.

(1. Yes - the graph is explicitly stated as remaining sparse (each depot connects to only a handful of others, not a large fraction of all 50,000), so an adjacency list remains far more space-efficient than an adjacency matrix, which would need 50,000 squared cells regardless of how few connections actually exist - exactly Sequence 12's dense-vs-sparse reasoning applied at a much larger scale. 2. Dijkstra remains necessary, not BFS - road journey times genuinely vary (the graph is weighted), and BFS has no mechanism for accounting for edge weights at all, as established above; using BFS here would risk recommending routes that are not actually fastest. 3. The O(V²) implementation's cost grows with the SQUARE of the number of vertices: going from 200 to 50,000 vertices (250x more) would multiply the O(V²) minimum-finding cost by roughly 250² = 62,500x, which would make route computation far too slow for a live application at this scale, even though the graph itself stays sparse. Replacing the plain linear-scan minimum-finding step with a priority queue (mentioned in Analyse, not implemented in this course) would reduce this to O((V+E) log V), which scales far more gracefully as V grows, particularly for a graph that remains sparse.)

Why this matters for the NEA

Route-planning, network, and logistics-style problems are common, substantial NEA project territory. Being able to justify not just which algorithm to implement, but why it's the right algorithm given the data's actual shape and scale — exactly the reasoning demonstrated in the synoptic task above — is precisely the kind of design justification AQA's NEA marking criteria reward.

Check your understanding

A network engineer proposes using Dijkstra's algorithm on a graph that includes one edge with a weight of −3 (representing a cost rebate on one specific route). Evaluate this proposal. (3 marks)

(Not appropriate as proposed. Dijkstra's correctness relies on non-negative edge weights, as shown above - a negative edge could offer a shorter path to an already-finalised vertex that the algorithm would never discover, since finalised vertices are never revisited. A different shortest-path algorithm designed to tolerate negative weights (such as Bellman-Ford, beyond this course's scope) would be needed instead, or the rebate would need to be modelled some other way that keeps all weights non-negative.)

Challenge

Extend the dijkstra function to also return the actual shortest path (the sequence of vertices), not just its total distance — hint: track, for each vertex, which neighbour it was most recently reached from during relaxation.

Looking ahead: Sequence 14 (Theory of Computation) moves from concrete algorithms to abstract reasoning about computation itself — decomposition, abstraction, and what can and can't be computed at all.