Lesson 6: Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds the shortest path from a single source node to every other node in a weighted graph with non negative edge weights.

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.