Dijkstra：Google Maps 怎麼幫你算最短路

BFS 為什麼不夠？

BFS 找最短路是按「邊的數量」算的。但 Google Maps 不是這樣—— 走 1 公里高速公路 vs 走 5 公里小路，前者更快。

真實世界的邊有「成本」（權重）：距離、時間、過路費。這時要用 Dijkstra。

像 BFS 一樣從起點擴散，但不是按步數，而是按「累計距離」。

每次從「目前已知最近的未拜訪點」出發更新它的鄰居。

從 A 出發找到所有點的最短距離：

維護一個「目前已知最短距離表」，初始時除起點外都是 ∞：

結果：A→A=0, A→B=4, A→C=2, A→D=3。

💡關鍵步驟

每次從未處理的點裡挑距離最小的處理。處理 X 時，更新 X 所有鄰居的距離：dist[鄰居] = min(舊距離, dist[X] + 邊權重) 這個更新叫 Relaxation（鬆弛）。

Algorithm Dijkstra(graph, source):

dist[v] ← ∞ for v in V

dist[source] ← 0

pq ← PriorityQueue() // 按距離排

pq.push((0, source))

while pq not empty:

(d, u) ← pq.pop() // 最小距離的點

if d > dist[u]: continue // 過時項

for (v, w) in graph[u]: // v 是鄰居，w 是邊權重

if dist[u] + w < dist[v]:

dist[v] ← dist[u] + w

pq.push((dist[v], v))

實作	時間
用陣列找最小	O(V²)
用 Priority Queue（heap）	O((V+E) log V) ← 實務版

⚠️Dijkstra 的限制

邊權重不能是負數！ 為什麼？Dijkstra 假設「一旦處理某個點，它的最短距離就確定了」。但負邊會讓「後來才發現的路徑更短」，違反假設。

有負邊要用 Bellman-Ford 演算法（這個比較進階，先記得名字就好）。

📝考試會這樣考

題型一：給帶權圖，列出 Dijkstra 每一輪的距離表。

訣竅：畫表格，每輪標清楚「處理哪個點、更新了哪些距離」。每一步都要寫出來，老師才能給分。

題型二：為什麼 Dijkstra 不適用於負邊？ 舉反例：A →(1)→ B →(-3)→ C，A 到 C 直接走 A→C 算成 ∞（沒這條邊），但繞 A→B→C = -2 才是最短。Dijkstra 會卡死。

題型三：Dijkstra vs BFS 差別。