Dijkstra's Shortest Path Algorithm

Breadth-first search finds the shortest path in an unweighted graph because every edge costs the same — one hop. But the graphs that model the real world are rarely unweighted: roads have lengths, network links have latencies, flights have fares. When edges carry different weights, "fewest edges" is no longer the same as "lowest total cost", and BFS gives the wrong answer. Dijkstra's algorithm, devised by Edsger Dijkstra in 1959, solves exactly this problem: it finds the minimum-total-weight path from a single source vertex to every other vertex, provided all edge weights are non-negative. At A-Level you must be able to trace it by hand on a small graph — maintaining the evolving distance table and choosing the next vertex from a priority queue — explain its greedy nature, state its complexity, and account for why negative weights break it.

---

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), Section 4.3 Fundamentals of algorithms, specifically 4.3.6 Optimisation algorithms (Dijkstra's shortest-path algorithm). The specification requires you to understand how the algorithm finds the shortest path between two vertices in a weighted graph and to be able to trace its operation. It builds on graphs (4.2.6) for the weighted representation, on priority queues (4.2.4) for selecting the next vertex efficiently, on the greedy paradigm introduced in the optimisation strand, and on the complexity vocabulary of 4.4.4 for its $O(V^2)$O(V2) / $O((V+E)\log V)$O((V+E)logV) analysis. It is the direct precursor to A* search (4.3.6), which adds a heuristic to the same machinery.

---

The Problem

Given a weighted graph and a chosen source vertex, find, for every other vertex, the path whose edge weights sum to the smallest possible total — the shortest path in the weighted sense — and report that total (and, usually, the route itself).

A concrete instance: model a road network as a graph in which vertices are junctions and each edge weight is the distance (or driving time) along a road. Running Dijkstra's algorithm from your home computes the shortest driving distance from home to every other junction at once — which is exactly the calculation a sat-nav performs.

---

How Dijkstra's Algorithm Works

The algorithm maintains a distance table recording the best-known distance to each vertex so far, together with a predecessor for reconstructing the route, and a set of vertices already finalised (visited). It selects the next vertex to finalise using a priority queue keyed on tentative distance — always taking the closest unfinalised vertex.

1. Set the tentative distance to the source as $0$0 and to every other vertex as $\infty$∞ (we do not yet know any route to them).
2. Mark all vertices as unvisited. Place all vertices in a priority queue keyed by tentative distance.
3. Select the unvisited vertex $u$u with the smallest tentative distance (initially the source).
4. Relax each edge from $u$u to an unvisited neighbour $v$v: compute newDist = dist[u] + weight(u, v); if newDist < dist[v], update dist[v] = newDist and set previous[v] = u.
5. Mark $u$u as visited (its distance is now final and will never change).
6. Repeat from step 3 until every vertex is visited (or until the specific target is finalised).

The single most important word here is relaxation — the act in step 4 of testing "is going via $u$u better than the best route I knew before?" and, if so, lowering the recorded distance. The algorithm's correctness rests on the greedy claim that the moment a vertex is selected as the closest unvisited one, its recorded distance is already optimal. This holds precisely because all weights are non-negative: any alternative route to $u$u would have to pass through some other unvisited vertex first, and that vertex is at least as far as $u$u, so the detour can only add cost — it can never beat the direct figure. (Remove the non-negativity assumption and this argument collapses, which is why the algorithm fails on negative edges.)

---

Pseudocode

PROCEDURE Dijkstra(graph, source)
    FOR EACH vertex v IN graph
        dist[v] = INFINITY
        previous[v] = NULL
        visited[v] = FALSE
    END FOR
    dist[source] = 0

    REPEAT V times
        u = unvisited vertex with the smallest dist[u]   // priority queue: extract-min
        visited[u] = TRUE

        FOR EACH neighbour v OF u
            IF NOT visited[v] THEN
                newDist = dist[u] + weight(u, v)
                IF newDist < dist[v] THEN                 // relaxation
                    dist[v] = newDist
                    previous[v] = u                       // remember the route
                END IF
            END IF
        END FOR
    END REPEAT
END PROCEDURE

A Python sketch using the standard-library priority queue (heapq) shows the priority-queue version concretely:

import heapq

def dijkstra(graph, source):
    # graph: dict vertex -> list of (neighbour, weight)
    dist = {v: float('inf') for v in graph}
    previous = {v: None for v in graph}
    dist[source] = 0
    pq = [(0, source)]            # (tentative distance, vertex)

    while pq:
        d, u = heapq.heappop(pq)  # extract the closest unfinalised vertex
        if d > dist[u]:
            continue              # stale entry, already improved upon
        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:     # relaxation
                dist[v] = new_dist
                previous[v] = u
                heapq.heappush(pq, (new_dist, v))
    return dist, previous

---

Full Worked Trace

Consider this weighted, undirected graph. We find the shortest paths from A to every vertex.

graph LR
  A["A"] ---|4| B["B"]
  A ---|2| C["C"]
  B ---|1| D["D"]
  C ---|3| D
  D ---|5| E["E"]

Edges and weights: A–B (4), A–C (2), B–D (1), C–D (3), D–E (5).

We will show two things at every iteration: the full distance table, and the priority queue (written as a list of vertex(distance) pairs, smallest first). The vertex extracted from the front of the queue each round is the one being finalised.

Initial state

Vertex	Distance	Previous	Visited
A	0	—	No
B	$\infty$∞	—	No
C	$\infty$∞	—	No
D	$\infty$∞	—	No
E	$\infty$∞	—	No

Priority queue: A(0), B(∞), C(∞), D(∞), E(∞)

Iteration 1 — extract A (distance 0)

Relax A's edges: B via A = $0+4=4$0+4=4 (improves $\infty$∞, update); C via A = $0+2=2$0+2=2 (improves $\infty$∞, update).

Vertex	Distance	Previous	Visited
A	0	—	Yes
B	4	A	No
C	2	A	No
D	$\infty$∞	—	No
E	$\infty$∞	—	No

Priority queue (unvisited): C(2), B(4), D(∞), E(∞) — C is now at the front.

Iteration 2 — extract C (distance 2)

C is chosen before B even though B was discovered first, because $2 < 4$2<4. Relax C's edges: D via C = $2+3=5$2+3=5 (improves $\infty$∞, update).

Vertex	Distance	Previous	Visited
A	0	—	Yes
B	4	A	No
C	2	A	Yes
D	5	C	No
E	$\infty$∞	—	No

Priority queue (unvisited): B(4), D(5), E(∞)

Iteration 3 — extract B (distance 4)

Relax B's edges: D via B = $4+1=5$4+1=5. The new figure $5$5 is not less than D's current $5$5, so no update — the existing route A→C→D is just as good. (Had B–D been weight 0, this would have tied; had it been negative, the no-update rule would have been wrong, foreshadowing the negative-weight failure.)

Vertex	Distance	Previous	Visited
A	0	—	Yes
B	4	A	Yes
C	2	A	Yes
D	5	C	No
E	$\infty$∞	—	No

Priority queue (unvisited): D(5), E(∞)

Iteration 4 — extract D (distance 5)

Relax D's edges: E via D = $5+5=10$5+5=10 (improves $\infty$∞, update).

Vertex	Distance	Previous	Visited
A	0	—	Yes
B	4	A	Yes
C	2	A	Yes
D	5	C	Yes
E	10	D	No

Priority queue (unvisited): E(10)

Iteration 5 — extract E (distance 10)

E has no unvisited neighbours, so there is nothing to relax. E is finalised and the queue is empty.

Reading off the answers

The distance column now holds the shortest distances; the route to any vertex is recovered by following the Previous pointers backwards to A and reversing.

Vertex	Shortest distance	Predecessor chain (reversed)	Shortest 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 how reconstructing D's route shows the value of the predecessor array: even though there are two ways to reach D with total cost 5 (A→C→D and A→B→D), the predecessor recorded is C, because that is the route that was current when D's distance reached its final value. Either route is a valid shortest path; the algorithm simply commits to one.

---

Complexity

Implementation of "extract the minimum"	Time complexity
Simple array / linear scan for the minimum	$O(V^2)$O(V2)
Binary heap (priority queue) + adjacency list	$O((V + E)\log V)$O((V+E)logV)

The cost is dominated by two repeated operations: selecting the closest unvisited vertex ($V$V times) and relaxing edges (each edge considered once). With a linear scan, each selection costs $O(V)$O(V), giving $O(V^2)$O(V2) overall — perfectly adequate for the small graphs in exams and for dense graphs where $E \approx V^2$E≈V2 anyway. With a binary heap, each extract-min and each decrease-key costs $O(\log V)$O(logV), and there are $O(V)$O(V) extractions and $O(E)$O(E) relaxations, giving $O((V+E)\log V)$O((V+E)logV) — much faster for sparse graphs (few edges), which describes most real road and network maps.

Space complexity is $O(V)$O(V) for the distance, predecessor and visited records (plus the priority queue, also $O(V)$O(V)).

---

Why Negative Weights Break Dijkstra's Algorithm

This is the most heavily examined limitation, so it deserves a concrete demonstration rather than a bald assertion. The algorithm's greedy guarantee — "a finalised vertex's distance is optimal" — assumes that adding edges can only increase a path's cost. A negative edge violates that, so a vertex can be finalised too early, before a cheaper route through a later, negative edge has been discovered.

Take this tiny directed graph:

graph LR
  A["A"] -->|2| B["B"]
  A -->|5| C["C"]
  C -->|-4| B

Run Dijkstra's from A. Iteration 1 finalises A and relaxes B to $2$2 and C to $5$5. Iteration 2 extracts B (distance $2$2, the smallest) and marks it visited and final. But the true shortest path to B is A→C→B $= 5 + (-4) = 1$=5+(−4)=1, which is less than 2. Because B was already finalised, the algorithm never revisits it and reports the wrong distance of 2. The non-negativity precondition is therefore not a technicality — it is the assumption the entire greedy argument depends on. For graphs that genuinely contain negative weights you must use the Bellman–Ford algorithm, which relaxes every edge $V-1$V−1 times and so tolerates negatives (and can even detect negative cycles, for which no shortest path exists at all).

Limitation	Explanation
No negative edge weights	Finalising the closest unvisited vertex assumes detours only add cost; a negative edge can make a later route cheaper, but the vertex is already locked, so the shorter path is missed (see the worked counter-example above).
No negative cycles	A cycle of negative total weight has no shortest path — you can loop forever lowering the cost — so neither Dijkstra nor any shortest-path algorithm is meaningful; Bellman–Ford at least detects this case.

---

Applications

Application	Example
GPS / sat-nav	Shortest or fastest driving route between two locations
Network routing	The OSPF (Open Shortest Path First) protocol runs Dijkstra's to build routing tables
Telecommunications	Lowest-cost or lowest-latency path through a link network
Game AI	Pathfinding for non-player characters across weighted terrain (often via A*, which generalises Dijkstra's)

Exam Tip: You will typically be given a small weighted graph (5–7 vertices) and asked to apply Dijkstra's step by step. Show the distance table after every iteration and clearly state which vertex you are finalising and why (it has the smallest tentative distance). Marks are lost for jumping to the final answer without the intermediate tables, and for finalising the wrong vertex (e.g. the most recently updated rather than the smallest).

---

Synoptic Links