Dijkstra’s Shortest Path Algorithm & Graph Theory - A Level Computer Science

Whether you are building GPS routing systems like Google Maps, designing network packet routers, or optimizing video game pathfinding, finding the shortest path across a network is a fundamental computing problem. For A-Level Computer Science (AQA, OCR, Edexcel), Dijkstra’s Algorithm is a core requirement you must be able to trace and implement.

1. What is Dijkstra's Algorithm?

Formulated by Dutch computer scientist Edsger W. Dijkstra in 1956, Dijkstra’s Algorithm is a greedy algorithm used to compute the shortest distance from a single starting vertex (node) to all other vertices in a weighted, directed or undirected graph with non-negative edge weights.

2. How the Algorithm Works Step-by-Step

1. Initialization: Assign every node a tentative distance value: set it to 0 for the start node and infinity ($\infty$) for all other nodes.
2. Unvisited Set: Mark all nodes as unvisited and create a list of unvisited vertices.
3. Select Current Node: Choose the unvisited node with the smallest tentative distance as the "current node".
4. Update Neighbors: For the current node, consider all its unvisited neighbors. Calculate their tentative distance through the current node:
   New Distance = Current Node Distance + Edge Weight
   If this calculated distance is less than the neighbor’s current assigned distance, update the distance (and record the current node as its predecessor).
5. Mark Visited: Once all neighbors are checked, mark the current node as visited. A visited node is never re-evaluated.
6. Repeat: Repeat steps 3–5 until the target node is marked as visited or all nodes have been processed.

3. Python Implementation (Adjacency Matrix / Dictionary)

Here is a clean Python implementation representing a graph using an adjacency dictionary and a priority queue via Python's built-in heapq module:

import heapq

def dijkstra(graph, start_node):
    # Initialize distances dictionary with infinity
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0
    
    # Priority queue stores tuples of (distance, node)
    priority_queue = [(0, start_node)]
    
    # Track predecessors to reconstruct the shortest path
    predecessors = {node: None for node in graph}

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

        # Nodes can be pushed multiple times; skip if we found a shorter path already
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # Relaxation step: update shortest distance if a better path is found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances, predecessors

# Example Weighted Graph Representation
network_graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
    'D': {'B': 5, 'C': 8, 'E': 2},
    'E': {'C': 10, 'D': 2}
}

shortest_distances, paths = dijkstra(network_graph, 'A')

print("Shortest Distances from Node A:")
for node, dist in shortest_distances.items():
    print(f"Path to {node}: Cost = {dist}")

4. Time & Space Complexity Analysis

A-Level exam questions frequently ask you to discuss algorithmic efficiency in terms of Big-O notation:

• $V$ represents the number of Vertices, and $E$ represents the number of Edges.
• Using a Min-Heap (Priority Queue) reduces search time from $O(V^2)$ to $O((V + E) \log V)$, making it viable for massive real-world road networks.

5. Test the Code Yourself

Copy the Python code above, head over to our interactive Python Console on the Computer Science page, and run it! Try adding new nodes to network_graph to map out your local bus routes or network topology.