Dijkstra 最短路徑演算法
Dijkstra 演算法：20 分鐘的極簡傑作
咖啡館、未婚妻，與沒有紙筆的靈感
1956 年的夏天，年輕的荷蘭電腦科學家 艾茲格·迪傑斯特拉 (Edsger W. Dijkstra) 正與未婚妻在阿姆斯特丹的一家咖啡館裡閒坐。當時的他面臨一個挑戰：為了向大眾展示新一代電腦 ARMAC 的威力，他需要編寫一個程式，計算出鹿特丹到格羅寧根最短路線。
傳說他僅用了 20 分鐘 就構思出了整個演算法。
最關鍵的一點是：當時他手頭沒有任何紙筆。正是這種「一窮二白」的困境，迫使迪傑斯特拉將演算法邏輯精簡到了極致——他必須讓整個演算法簡單到能完全裝進大腦裡而不出任何錯。他刻意迴避了一切複雜的數學推導，因為他希望哪怕是非數學家也能聽懂電腦是如何「思考」距離的。
迪傑斯特拉的洞察揭示了一個真理：最偉大的解決方案往往是最簡單的。時至今日，你的 GPS 導航、網路路由器，乃至社群媒體的推薦流，都在沿用這 20 分鐘「無紙化」誕生的智慧。
為什麼需要它？
想像你在開發一個導航 App。在你的世界裡，「距離」不只是公里數，更是時間或成本。
- 高速公路： 10 公里耗時 5 分鐘（成本 = 5）。
- 市區道路： 2 公里耗時 10 分鐘（成本 = 10）。
簡單的搜尋演算法會選擇市區道路，因為它只有「一跳」。但你想要的是最快的路線。你需要一個能夠尊重每條路「權重」的演算法。
演算法是如何「思考」的
Dijkstra 演算法的工作方式，其實非常「固執」。
一開始，它對世界一無所知，表現得非常謙卑：
- 它標記起點的距離為 0；
- 它標記其他所有目的地為**「遙不可及」** ()。
接下來的每一步，它都進行同一種充滿儀式感的重複：
它會環顧四周，挑選那個目前看起來離起點最近、但還沒被確認過的節點。一旦選中了它，演算法就會鄭重其事地宣布：
「到這裡為止，這條路官方認證不可能再更短了。」
只有在宣布完之後，它才開始試探性地詢問這個節點的鄰居：
「如果我從這裡再多走一步到你那裡，你會不會比之前記錄的路更近一點？」
如果答案是肯定的，它就毫不猶豫地修正記錄。這個過程不斷重複——挑選最近的，更新鄰居——直到所有節點都被確認，或者你已經抵達終點。
「當下」的邏輯
在每一步中，演算法只關心一件事：此刻，哪個選擇的代價最低？
它不會回頭重新考慮已經確認的決定，也不會試圖猜測未來的可能性。這種「只看當下最優解」的策略，在演算法世界裡有一個專門的名字——貪婪演算法 (Greedy Algorithm)。
工程決策：為什麼它在生產中勝出
在學術論文裡，我們談論複雜度 。但在現實的工程實踐中，工程師選擇 Dijkstra 是因為它的**「性價比」**。
透過配合 最小優先佇列，它的性能足以支撐：
- 城市級的路網導航。
- 中等規模的微服務依賴圖分析。
- 物流系統的即時路徑計算。
它雖然不是最「聰明」的演算法（那是 A* 搜尋），但由於它不依賴複雜的啟發式估算，它的執行極其可靠且易於偵錯。它是工業界最值得信賴的「老黃牛」。
實作參考 (Python)
import heapq
def dijkstra(graph, start):
# 1. 初始化：除了起點，所有人都是遙不可及的
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 優先佇列，儲存格式為：(目前距離, 節點ID)
# Python 的 heapq 預設實作的是小頂堆
pq = [(0, start)]
while pq:
current_dist, u = heapq.heappop(pq)
# 過期條目檢查：如果你已經找到了更近的路，就忽略這個舊記錄
if current_dist > distances[u]:
continue
# 詢問鄰居
for v, weight in graph[u].items():
distance = current_dist + weight
# 試探性詢問：走這條路會不會更近？
if distance < distances[v]:
distances[v] = distance
heapq.heappush(pq, (distance, v))
return distances
# 使用範例:
# graph = {'A': {'B': 5, 'C': 10}, 'B': {'C': 3}, 'C': {}}
# print(dijkstra(graph, 'A'))小結
回到 1956 年那家咖啡館。沒有黑板，沒有公式，甚至沒有一張餐巾紙。只有一個工程師在反覆追問自己：
「如果我一次只能記住一件事，路徑應該怎麼被找到？」
迪傑斯特拉給出的答案簡單到令人難以置信。也正因為如此，七十年後的今天，整個數位世界依然在追隨他的腳步。