Dijkstra's Shortest Path Algorithm (OCR A-Level Computer Science): Revision Notes

Dijkstra's Shortest Path Algorithm

Overview

Dijkstra's Shortest Path Algorithm is a graph traversal algorithm used to find the shortest path from a source node to all other nodes in a weighted graph. The algorithm guarantees the shortest path for graphs with non-negative edge weights.

How Dijkstra's Algorithm Works

• Input: A weighted graph, a starting node (source).
• Output: The shortest path from the source node to all other nodes.

Steps:

1. Initialise:

• Set the distance to the source node as 0 and all other nodes as infinity (∞).
• Mark all nodes as unvisited.

2. Visit Nodes:

• Start with the source node.
• For each unvisited neighbour, calculate the tentative distance from the source.
• If this distance is smaller than the previously recorded distance, update it.

3. Mark Node as Visited:

• Once all neighbours of the current node are evaluated, mark it as visited. A visited node will not be revisited.

4. Repeat:

• Move to the unvisited node with the smallest tentative distance.
• Repeat steps 2–4 until all nodes are visited or the shortest path to the target node is found (if only specific node distances are required).

Properties of Dijkstra's Algorithm

• Greedy Algorithm: Always selects the node with the smallest known distance.
• Time Complexity:
  • O(V²) for simple implementation using an adjacency matrix.
  • O((V + E) log V) with a priority queue (using a binary heap).
• Space Complexity: O(V + E) for adjacency list storage.

Pseudocode for Dijkstra's Algorithm

METHOD Dijkstra(graph, source)
    dist ← array of size graph.length filled with ∞
    dist[source] ← 0
    visited ← empty set

    WHILE there are unvisited nodes
        current ← node with smallest distance in dist
        visited.add(current)

        FOR each neighbour of current
            IF neighbour NOT IN visited
                tentative_distance ← dist[current] + weight(current, neighbour)
                IF tentative_distance < dist[neighbour]
                    dist[neighbour] ← tentative_distance
    ENDWHILE

    RETURN dist

Python Implementation

import heapq  # Priority queue for efficient node selection

def dijkstra(graph, source):
    # Initialise distances and priority queue
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    priority_queue = [(0, source)]  # (distance, node)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        for neighbour, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < dist[neighbour]:
                dist[neighbour] = distance
                heapq.heappush(priority_queue, (distance, neighbour))

    return dist

# Example graph as an adjacency list
graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1)],
    'C': [('B', 2), ('D', 5)],
    'D': [('E', 3)],
    'E': []
}

# Compute shortest paths from source 'A'
distances = dijkstra(graph, 'A')
print(distances)  # Output: {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

Tracing Dijkstra's Algorithm

Given the following graph:

From	To	Weight
A	B	2
A	C	5
B	C	1
B	D	4
C	D	2
D	E	1

5. Start at A (distance = 0).
6. Visit B (distance = 2 via A).
7. Visit C (distance = 3 via B).
8. Visit D (distance = 5 via C).
9. Visit E (distance = 6 via D).

Note Summary