Lesson 6: Dijkstra's Shortest Path Algorithm

The GPS Problem

It's 7:45 AM. You're late for a meeting across town. Your GPS app shows you're at location A and needs to get you to location B as fast as possible. There are a dozen possible routes, each with different travel times depending on roads, traffic, and distance.

Your GPS doesn't guess or try every possible route. It uses a precise algorithm that guarantees the fastest path: Dijkstra's algorithm.

This algorithm was devised by computer scientist Edsger Dijkstra in 1956, reportedly in about 20 minutes while sitting in a café with his fiancée. It remains one of the most practically important algorithms ever created.

Weighted Graphs: Adding Costs to Connections

In the previous lesson, all edges were equal — each connection had the same "cost" of 1. Real-world networks are different. Roads have different speeds, flight routes have different prices, network cables have different latencies.

A weighted graph assigns a numerical value (weight) to each edge:

City Map with Travel Times (minutes):

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

As an adjacency list:

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2},
    'C': {'A': 4, 'D': 1, 'E': 5},
    'D': {'B': 2, 'C': 1, 'E': 3},
    'E': {'C': 5, 'D': 3}
}

Question: What is the shortest path from A to E?

Naive answer: A → C → E = 4 + 5 = 9 minutes Better path: A → B → D → E = 1 + 2 + 3 = 6 minutes Even better: A → B → D → C → E = 1 + 2 + 1 + 5 = 9 minutes (worse)

The optimal is 6 minutes, but you'd need to check carefully. With a larger graph, manual checking is impossible.

Dijkstra's Algorithm: The Greedy Approach

The Core Idea

Dijkstra maintains a table of the best known distance from the start to every node, updating it as better paths are discovered.

The greedy insight: At each step, process the unvisited node with the smallest known distance. Why? Because once you've confirmed the shortest distance to a node, no future path through unvisited nodes can improve it (assuming all weights are non-negative).

Algorithm Steps

1. Initialize all distances to infinity except start node (distance = 0)
2. Add start node to a priority queue
3. While the priority queue is not empty:
   a. Extract the node with the smallest distance
   b. If we've already found a better path to this node, skip it
   c. For each neighbor: if current path is shorter than known best, update it
   d. Add updated neighbors to the priority queue
4. Return the distances table

Visual trace on our example (start = A):

Step 1: distances = {A:0, B:inf, C:inf, D:inf, E:inf}
        queue = [(0, A)]

Step 2: Process A (dist=0)
        Update B: 0+1=1 < inf → distances[B] = 1
        Update C: 0+4=4 < inf → distances[C] = 4
        queue = [(1, B), (4, C)]

Step 3: Process B (dist=1) — smallest in queue
        Update D: 1+2=3 < inf → distances[D] = 3
        queue = [(3, D), (4, C)]

Step 4: Process D (dist=3) — smallest in queue
        Update C: 3+1=4 == 4 → no improvement
        Update E: 3+3=6 < inf → distances[E] = 6
        queue = [(4, C), (6, E)]

Step 5: Process C (dist=4) — smallest in queue
        Update E: 4+5=9 > 6 → no improvement
        queue = [(6, E)]

Step 6: Process E (dist=6)
        No improvements possible.
        queue = []

Final: {A:0, B:1, C:4, D:3, E:6}

Full Implementation

import heapq

def dijkstra(graph, start):
    # Initialize all distances to infinity
    distances = {node: float('inf') for node in graph}
    distances[start] = 0               # Distance to start is 0

    # Priority queue: (distance, node)
    pq = [(0, start)]

    # Track previous nodes for path reconstruction
    previous = {node: None for node in graph}

    while pq:
        curr_dist, curr_node = heapq.heappop(pq)   # Get node with smallest distance

        # If we already found a better path to this node, skip
        if curr_dist > distances[curr_node]:
            continue

        # Examine all neighbors
        for neighbor, weight in graph[curr_node].items():
            dist = curr_dist + weight              # Distance through curr_node

            if dist < distances[neighbor]:         # Found a shorter path
                distances[neighbor] = dist
                previous[neighbor] = curr_node     # Track where we came from
                heapq.heappush(pq, (dist, neighbor))

    return distances, previous

def reconstruct_path(previous, start, end):
    """Trace back through 'previous' to build the path from start to end."""
    path = []
    current = end

    while current is not None:
        path.append(current)
        current = previous[current]

    path.reverse()

    # Check if a valid path exists
    if path[0] == start:
        return path
    return None

# --- Full example ---
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2},
    'C': {'A': 4, 'D': 1, 'E': 5},
    'D': {'B': 2, 'C': 1, 'E': 3},
    'E': {'C': 5, 'D': 3}
}

distances, previous = dijkstra(graph, 'A')

print("Shortest distances from A:")
for node, dist in sorted(distances.items()):
    print(f"  A → {node}: {dist} minutes")

print()
print("Shortest path from A to E:")
path = reconstruct_path(previous, 'A', 'E')
print(f"  {' → '.join(path)} = {distances['E']} minutes")

Output:

Shortest distances from A:
  A → A: 0 minutes
  A → B: 1 minutes
  A → C: 4 minutes
  A → D: 3 minutes
  A → E: 6 minutes

Shortest path from A to E:
  A → B → D → E = 6 minutes

The Priority Queue: Why It's Essential

The key to Dijkstra's efficiency is using a min-heap priority queue (heapq in Python). Without it, finding the minimum distance node requires scanning all nodes — O(V) per step — giving O(V²) total.

With a priority queue:

• Extracting the minimum costs O(log V)
• Each edge may trigger a push costing O(log V)
• Total: O((V + E) log V)

Without priority queue: O(V²)   — acceptable for dense graphs
With priority queue:    O((V+E) log V) — better for sparse graphs

For a city map with 1 million nodes but only 5 million edges (sparse), the difference is enormous:

• O(V²) = 1,000,000,000,000 operations
• O((V+E) log V) ≈ 120,000,000 operations

A Simpler Example: Verified Output

# The exact graph from the lesson introduction
graph = {'A': {'B':1,'C':4}, 'B': {'C':2,'D':5}, 'C': {'D':1}, 'D': {}}
distances, _ = dijkstra(graph, 'A')
print(distances)
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Output:

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

Path to C: A → B → C = 1 + 2 = 3 (shorter than A → C directly = 4) Path to D: A → B → C → D = 1 + 2 + 1 = 4 (shorter than A → B → D = 1 + 5 = 6)

Critical Limitation: Negative Weights

Dijkstra's algorithm does not work with negative edge weights. Here's why:

A ---(-3)--- B ---(5)--- C
     \                  /
      -------2-----------

If A→B costs -3, going through B makes A→C = -3 + 5 = 2, better than A→C = 2. But Dijkstra might process C before B (since 2 < -3+5=2 initially), locking in the wrong answer.

For negative weights, use Bellman-Ford algorithm:

• Time complexity: O(V × E) — slower than Dijkstra
• Handles negative weights correctly
• Can also detect negative cycles (where shortest path is undefined)

Real-World Applications

GPS Navigation: Google Maps, Apple Maps, and Waze all use variants of Dijkstra's (combined with heuristics like A* for speed) to compute driving routes.

Network Routing: The OSPF (Open Shortest Path First) protocol, used by routers worldwide, is a direct implementation of Dijkstra's algorithm. Every packet you send over the internet may be routed using this algorithm.

Flight Planning: Airlines compute minimum-cost routes through hub networks using shortest path algorithms.

Social Networks: Finding the minimum number of introductions to reach someone ("degrees of separation").

Video Games: Pathfinding for NPCs (non-player characters) navigating terrain uses A*, which is an informed variant of Dijkstra's.

Complexity Summary

Dijkstra's algorithm represents a beautiful union of data structures and algorithmic thinking: a greedy strategy made efficient by the right choice of supporting data structure. Understanding it deeply — not just the code, but why the greedy approach is safe — is a mark of genuine algorithmic maturity.