Dijkstra 演算法：加權圖的最短路徑

BFS 可以找到「最少步數」的路徑，但現實世界中的路徑規劃不只是算步數——我們需要考慮「距離」、「時間」、「交通成本」。

Dijkstra 演算法就是為了解決這個問題而生。它由荷蘭電腦科學家 Edsger W. Dijkstra 在 1956 年提出，至今仍是 Google Maps、Apple Maps 等所有導航系統的核心基礎。

Dijkstra 的核心概念

Dijkstra 的直覺非常簡單：「從起點開始，總是選擇目前已知最短的路径繼續探索。」

類比：快遞配送

想像你是一個快遞員，要從台北車站送貨到高雄。你不知道所有道路的長度，但你可以一步步嘗試：

1. 先看台北車站旁邊的路口，記下每個路口的距離
2. 從最近的鄰居開始，看看從那裡出發可以到哪些新地方
3. 如果發現「經由這個鄰居到某個路口」比「之前記錄的路線」更短，就更新記錄
4. 重複直到抵達高雄為止

這就是 Dijkstra 的本質！

演算法流程

import heapq

def dijkstra(graph, start, goal):
    """
    Dijkstra 最短路徑演算法
    
    graph: dict — 鄰接表，格式 {node: [(neighbor, weight), ...]}
    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')  # 無法到達

在台灣高鐵圖上執行 Dijkstra

# === 使用高鐵圖測試 Dijkstra ===
hsr_graph = {
    '南港': [('台北', 4)],
    '台北': [('南港', 4), ('板橋', 7)],
    '板橋': [('台北', 7), ('桃園', 34)],
    '桃園': [('板橋', 34), ('新竹', 39)],
    '新竹': [('桃園', 39), ('苗栗', 33)],
    '苗栗': [('新竹', 33), ('台中', 52)],
    '台中': [('苗栗', 52), ('彰化', 17)],
    '彰化': [('台中', 17), ('雲林', 25)],
    '雲林': [('彰化', 25), ('嘉義', 20)],
    '嘉義': [('雲林', 20), ('台南', 65)],
    '台南': [('嘉義', 65), ('左營', 40)],
    '左營': [('台南', 40)],
}

# 測試
path, dist = dijkstra(hsr_graph, '南港', '左營')
print(f"南港 → 左營 最短路徑: {' → '.join(path)}")
print(f"總距離: {dist} 公里")

# 與 NetworkX 的結果比較
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, '南港', '左營', weight='weight')
nx_dist = nx.shortest_path_length(G, '南港', '左營', weight='weight')
print(f"\nNetworkX 結果: {' → '.join(nx_path)}")
print(f"NetworkX 距離: {nx_dist} 公里")

Dijkstra 視覺化

import matplotlib.pyplot as plt
import networkx as nx

# 視覺化 Dijkstra 的搜尋過程
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, '南港', '左營', 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 == '南港':
        node_colors.append('green')
    elif node == '左營':
        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 最短路徑：南港 → 左營（紅色高亮）", fontsize=14)
plt.axis('off')
plt.tight_layout()
plt.show()

時間複雜度分析

| 實作方式 | 時間複雜度 | 空間複雜度 | |---------|-----------|-----------| | 簡單陣列 (Array) | O(V²) | O(V) | | 二元堆積 (Binary Heap) | O((V+E)log V) | O(V) | | 斐波那契堆積 (Fibonacci Heap) | O(E + V log V) | O(V) |

其中 V = 節點數量，E = 邊緣數量。

實務上，我們使用**二元堆積（即 Priority Queue）**實作，也就是 heapq 版本。

Dijkstra 的適用場景與限制

✅ 適用場景

• 地圖導航（Google Maps、Apple Maps）
• 網路路由（OSPF 協定）
• 物流配送最佳化
• 社交網路「影響力傳播」分析

❌ 限制

• 不能處理負權重邊：如果道路有「負距離」（例如某些獎勵路徑），Dijkstra 會失敗
• 需要知道所有節點：Dijkstra 是全域搜尋，不適合未知環境
• 當圖形非常大時：在數百萬節點的圖中，Dijkstra 可能太慢

使用 Vibe Coding 實作 Dijkstra

🔥 【Dijkstra 詠唱範例】 「我想用 Dijkstra 規劃台北市區的uber接送路線： 1. 建立一個圖形包含 50 個路口，隨機生成道路與距離。 2. 實作 Dijkstra 演算法找到最短路徑。 3. 用 NetworkX 畫出圖形與最短路徑高亮。 4. 顯示 Dijkstra 每一步擴張的過程（探索區域視覺化）。 5. 比較 Dijkstra 與 BFS 在加權圖上的結果差異。」

本日總結

在本章中，你學到了：

1. ✅ Dijkstra 核心思想：從起點出發，總是選目前最短的路繼續走
2. ✅ Priority Queue 實作：使用 heapq 優化搜尋效率
3. ✅ 台灣高鐵實戰：在真實資料上計算最短路徑
4. ✅ 視覺化：畫出最短路徑與探索過程
5. ✅ 時間複雜度：理解 V 與 E 對效能的影響
6. ✅ 限制與替代方案：何時不能用 Dijkstra

下一章，我們將進入最令人興奮的主題——A* 搜尋演算法！