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

Maintain a distance table with the current shortest known distance from the source to every vertex. Initially, the source has distance 0 and all others have distance infinity. Repeatedly select the unvisited vertex with the smallest distance and update its neighbours.

Algorithm Steps

1. Set the distance to the source vertex to 0, and all other vertices to infinity.
2. Mark all vertices as unvisited. Set the source as the current vertex.
3. For the current vertex, examine all unvisited neighbours:
   • Calculate the distance through the current vertex: current distance + edge weight.
   • If this is less than the neighbour's recorded distance, update it.
4. Mark the current vertex as visited (it will not be reconsidered).
5. Select the unvisited vertex with the smallest distance as the new current vertex.
6. Repeat steps 3-5 until all vertices are visited or the destination is reached.

Pseudocode (OCR Style)

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

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)]

    while heap:
        current_dist, current = heapq.heappop(heap)
        if current in visited:
            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

---

Worked Example

Consider this weighted graph:

    A --4-- B
    |       |\
    2       1  7
    |       |   \
    C --3-- D --5-- E

Adjacency list:

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)]

Find shortest paths from A:

Step-by-Step Trace