Dijkstra 最短路徑演算法是一種用於計算從單一源點到圖中所有其他節點的最短路徑的經典演算法。這個演算法適用於加權圖，其中邊的權重必須是非負的，核心思想是每次選擇「距離起點最近」的尚未處理節點，並用它來更新鄰居的最短距離，這種策略屬於貪心演算法 (Greedy Algorithm)

演算法步驟

• 初始化
  • 將所有節點的距離設為無限大，除了起始節點，其距離設為 0
  • 將所有節點標記為未訪問
  • 使用一個優先佇列 (通常是最小堆) 來追蹤當前已知的最短距離
• 選擇節點
  • 從優先佇列中選擇距離起始節點最近的未訪問節點，將其標記為訪問過
• 更新鄰居
  • 對於該節點的每一個鄰居，計算從起始節點經過該節點到鄰居的距離
  • 如果這個距離小於目前記錄的距離，則更新鄰居的距離，並將其加入優先佇列
• 重複
  • 重複步驟 2 和 3，直到所有節點都被訪問過
• 結束
  • 當所有節點都被訪問過後，從起始節點到其他所有節點的最短路徑距離即已計算完成

例子

假設有一個圖如下:

A --(1)--> B
A --(4)--> C
B --(2)--> C
B --(5)--> D
C --(1)--> D

• 起始節點為 A
• 初始化: A 的距離為 0，B、C、D 的距離為無限大
• 從 A 開始，更新 B 和 C 的距離
• 選擇距離最小的 B，更新 C 和 D 的距離
• 選擇距離最小的 C，更新 D 的距離
• 最後選擇 D，所有節點都被訪問過

複雜度

Dijkstra 演算法的時間複雜度取決於使用的資料結構。若使用二元堆，時間複雜度為 $O((V + E) \log V)$，其中 $V$ 是節點數，$E$ 是邊數

程式碼

import heapq

def dijkstra(graph, start):
    # graph: adjacency list 格式 {u: [(v, weight), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    
    # 最小堆 (priority queue)
    pq = [(0, start)]  
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        # 如果已經不是最短路徑，跳過
        if current_dist > dist[u]:
            continue
        
        for v, weight in graph[u]:
            distance = current_dist + weight
            if distance < dist[v]:
                dist[v] = distance
                heapq.heappush(pq, (distance, v))
    
    return dist

# 測試
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}

print(dijkstra(graph, 0))  
# 輸出: {0: 0, 1: 3, 2: 1, 3: 4}

優缺點

結語

Dijkstra 演算法是圖論中最重要的演算法之一，能高效解決單源最短路徑問題，它的貪心思想簡單卻強大，應用範圍極廣，從日常導航到金融網路分析都能見到它的身影