Dijkstra: Shortest Path in Weighted Graphs

BFS finds the path with fewest steps - but real-world pathfinding is not just about steps. We need distances, time, and traffic costs.

Dijkstra was invented by Dutch computer scientist Edsger W. Dijkstra in 1956. It remains the foundation of Google Maps, Apple Maps, and all navigation systems.

Why Dijkstra? (Why)

Why BFS is not enough:

• BFS only works on unweighted graphs (all edges equal)
• Real roads have different lengths, times, and costs
• Dijkstra handles all weighted graph scenarios

What Is Dijkstra? (What)

Dijkstra intuition: start from the start node, always pick the path with the shortest known distance so far.

How Dijkstra Works (How)

import heapq

def dijkstra(graph, start, goal):
    pq = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    parent = {start: None}
    visited = set()
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        if current_dist > distances[current]:
            continue
        visited.add(current)
        if current == goal:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]
            return list(reversed(path)), distances[goal]
        for neighbor, weight in graph[current]:
            if neighbor in visited:
                continue
            new_dist = current_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                parent[neighbor] = current
                heapq.heappush(pq, (new_dist, neighbor))
    return None, float('inf')

Hands-On: Taiwan High-Speed Rail

hsr_graph = {
    'Nangang': [('Taipei', 4)],
    'Taipei': [('Nangang',4), ('Banqiao',7)],
    'Banqiao': [('Taipei',7), ('Taoyuan',34)],
    'Taoyuan': [('Banqiao',34), ('Hsinchu',39)],
    'Hsinchu': [('Taoyuan',39), ('Miaoli',33)],
    'Miaoli': [('Hsinchu',33), ('Taichung',52)],
    'Taichung': [('Miaoli',52), ('Changhua',17)],
    'Changhua': [('Taichung',17), ('Yunlin',25)],
    'Yunlin': [('Changhua',25), ('Chiayi',20)],
    'Chiayi': [('Yunlin',20), ('Tainan',65)],
    'Tainan': [('Chiayi',65), ('Zuoying',40)],
    'Zuoying': [('Tainan',40)],
}

path, dist = dijkstra(hsr_graph, 'Nangang', 'Zuoying')
print(f"Shortest path: {' -> '.join(path)}")
print(f"Total distance: {dist} km")

import networkx as nx
G = nx.Graph()
for node, neighbors in hsr_graph.items():
    for neighbor, weight in neighbors:
        G.add_edge(node, neighbor, weight=weight)
nx_path = nx.shortest_path(G, 'Nangang', 'Zuoying', weight='weight')
nx_dist = nx.shortest_path_length(G, 'Nangang', 'Zuoying', weight='weight')
print(f"NetworkX: {nx_dist} km, path matches: {path == nx_path}")

Dijkstra vs BFS

| Feature | BFS | Dijkstra | |---------|:---:|:--------:| | Edge weights | All equal | Any weights | | Shortest path | By edge count | By total weight | | Data structure | Queue | Priority Queue | | Time complexity | O(V+E) | O((V+E)log V) | | Negative edges | Works | Fails |

Time Complexity

| Implementation | Time | Best For | |:--------------|:----:|----------| | Array (no PQ) | O(V^2) | Dense graphs | | Binary Heap | O((V+E)log V) | General use | | Fibonacci Heap | O(E + V log V) | Extremely large |

Real-World Applications

• Google Maps: Dijkstra + real-time traffic data
• Network routing: OSPF protocol uses Dijkstra
• Logistics: Optimize delivery routes
• Social networks: Friend recommendations

Limitations

1. Cannot handle negative edge weights (use Bellman-Ford)
2. Requires full graph knowledge
3. Too slow on huge graphs (millions of nodes)

Summary

1. Dijkstra: always pick shortest known path, uses Priority Queue
2. Taiwan HSR: real-world shortest path calculation
3. Time: O((V+E)log V) with Binary Heap
4. Limitations: no negative edges, not for unknown environments

Greedy Proof: Why Dijkstra Always Works

Dijkstra is a greedy algorithm. Each step picks the unprocessed node with smallest distance. The cut property guarantees once a node is processed, its distance is truly optimal.

Every time we pop a node from the priority queue, its distance is the shortest possible. Proof by contradiction: if there were a shorter path, it would have to go through some unprocessed node, but that node has a larger distance by definition - contradiction.

Visualization: Dijkstra Step by Step

import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()
for node, neighbors in hsr_graph.items():
    for neighbor, weight in neighbors:
        G.add_edge(node, neighbor, weight=weight)

path = nx.shortest_path(G, 'Nangang', 'Zuoying', weight='weight')
pos = {s: (i, 0) for i, s in enumerate(G.nodes())}

plt.figure(figsize=(16, 4))
nx.draw_networkx_edges(G, pos, edge_color='gray', width=1, alpha=0.5)

path_edges = list(zip(path[:-1], path[1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges,
                       edge_color='red', width=3, alpha=0.8)

node_colors = []
for node in G.nodes():
    if node == 'Nangang': node_colors.append('green')
    elif node == 'Zuoying': node_colors.append('red')
    elif node in path: node_colors.append('lightblue')
    else: node_colors.append('lightgray')

nx.draw_networkx_nodes(G, pos, node_color=node_colors, node_size=2000)
nx.draw_networkx_labels(G, pos, font_size=10, font_weight='bold')

edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=8)

plt.title("Dijkstra: Nangang to Zuoying (shortest path in red)", fontsize=14)
plt.axis('off')
plt.tight_layout()
plt.show()

Vibe Coding for Dijkstra

[Dijkstra Prompt Example] "I want to plan Uber pickup routes in Taipei using Dijkstra:" "1. Build a graph with 50 intersections with random road distances." "2. Implement Dijkstra to find the shortest path." "3. Visualize with NetworkX highlighting the shortest path." "4. Show the expansion process step by step (explored area visualization)." "5. Compare Dijkstra vs BFS results on weighted graphs."

Dijkstra vs BFS In-Depth

| Compare | BFS | Dijkstra | |---------|:---:|:--------:| | Edge weights | All equal | Any positive weights | | Shortest by | Edge count | Total weight | | Data struct | Queue (FIFO) | Priority Queue (Min-Heap) | | Time | O(V+E) | O((V+E)log V) | | Negative edges | Works | Fails |

BFS guarantees shortest path but only for unweighted graphs. Dijkstra handles weighted graphs but cannot handle negative edges (use Bellman-Ford).

Memory & Performance Considerations

| Implementation | Time | Space | When to Use | |:--------------|:----:|:-----:|-------------| | Array Scan | O(V^2) | O(V) | Dense graphs (E ~ V^2) | | Binary Heap | O((V+E)log V) | O(V) | General purpose | | Fibonacci Heap | O(E + VlogV) | O(V) | Extremely large graphs |

In 99% of real applications, Binary Heap (Priority Queue via heapq) is the right choice.

Next Chapter: A* Algorithm

Dijkstra guarantees optimality but is slow on large maps. A* adds heuristics to accelerate search - the standard for games and navigation.