Dijkstra 演算法教學：原理、程式碼與時間複雜度

Dijkstra 演算法解決什麼問題

廣度優先搜尋找的是邊數最少的路徑，但道路、網路連線與航班各有不同的長度、成本或延遲。Dijkstra 演算法解決的是這類加權圖上的單源最短路徑問題：給定一個起點，找出到其他每個節點的最小總成本，以及達成該成本的路徑。

Edsger W. Dijkstra 於 1959 年在論文〈A note on two problems in connexion with graphs〉中發表了這個演算法。

用白話說明原理

1. 把起點的距離設為 0，其他所有節點的距離設為無限大。
2. 挑出距離最小且尚未確定的節點，它的距離此時即為最終結果。
3. 對它的每條外向邊 u → v（權重為 w）進行鬆弛：如果 dist[u] + w < dist[v]，就設定 dist[v] = dist[u] + w，並記下 u 是 v 的父節點。
4. 重複步驟 2 和 3，直到所有可到達的節點都已確定。

為什麼距離最小的節點就是最終結果？因為到達該節點的其他路線都必須經過某個距離至少一樣大的節點，而在權重非負的情況下，剩下的邊只會讓成本增加。

逐步範例

有向圖的邊為 A→B（4）、A→C（1）、C→B（2）、B→D（1）、C→D（5）、D→E（3），從 A 出發。

B 一開始透過直接的邊得到距離 4，之後經由 C 改善為 3。到 E 的最短路徑是 A → C → B → D → E，總成本為 1 + 2 + 1 + 3 = 7。

使用 heapq 的 Python 實作

Python 的 heapq 模組提供二元最小堆積。它沒有「降低鍵值」的操作，所以每當距離有改善時，就推入一組新的 (distance, node)，並在彈出時略過過期的組合。這種做法稱為惰性刪除（lazy deletion）。

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

若要取得到某個目標的路徑，沿著父節點連結往回走到起點即可：

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

如果只需要到單一目標的距離，當該目標從堆積中彈出時就可以停止：此刻它的距離已是最終結果。

時間與空間複雜度

空間為 O(V + E)，用於儲存圖、距離與父節點對應表，以及堆積。

變化版本與常見錯誤

• 省略 if d > dist[u]: continue 這個檢查並不會算錯，但演算法會去處理過期的資料，可能慢上許多。
• 只推入節點而不是 (distance, node)，會讓堆積的排序失去意義。
• 如果節點是無法比較的物件，距離相同時 heapq 會去比較節點本身，並拋出 TypeError。請改推入 (distance, counter, node)，並使用唯一的計數器。
• A* 搜尋就是在優先順序中加入啟發函式的 Dijkstra；當你對剩餘距離有良好的估計時，它能探索較少的節點。
• 雙向 Dijkstra 同時從起點和終點出發，兩邊的搜尋相遇時停止。

何時使用與實際應用

• 路由：OSPF、IS-IS 等鏈路狀態路由協定，其最短路徑優先計算就是以 Dijkstra 演算法為基礎。
• 地圖與導航：實際的商用系統會在 Dijkstra 式搜尋之上加入預處理。
• 面試題目：網路延遲時間、最便宜的航班（有轉機次數限制）、網格中的最小體力路徑，以及任何圖上的「最小總成本」問題。