Dijkstra單源最短路徑

01為什麼需要它

看到這些關鍵字就想到它：最短／最快／最便宜的路徑、邊有非負權重、成本沿路徑累加、單一起點到所有點、每格代價不同的網格、優先佇列加鬆弛。

02核心概念

BFS 能在無權圖上找最短路徑，是因為佇列的先進先出剛好等於「距離由小到大」。邊一旦有權重，這個對應就斷了：走兩段短路可能比走一段長路更近。Dijkstra 把佇列換成最小堆積，為每個節點維護目前已知的最短距離 dist（一開始是 ∞）。每一輪取出「還沒確定、而且 dist 最小」的節點 u，宣告它的距離確定，再用它的每條邊做鬆弛：若 dist[u] + w < dist[v]，就把 dist[v] 改小，並記下 parent[v] = u。節點被確定的順序，就是它們離起點由近到遠的順序。

為什麼取出的當下就能確定？設 u 是未確定節點裡 dist 最小的，值為 d。任何一條從起點到 u 的路徑，都得在某處第一次踏出「已確定集合」，走到某個未確定的節點 y。y 的前一個節點已經確定、確定時也用這條邊鬆弛過 y，所以走到 y 的長度至少是 dist[y]，而 dist[y] ≥ d；剩下從 y 到 u 的邊權都非負，只會讓總長再變大。因此沒有路徑比 d 更短，這就是這個貪婪選擇正確的原因。證明裡用到了「邊權非負」，負權邊會直接打破它：A→B = 2、A→C = 3、C→B = −2，B 在第二輪就以 2 被確定，但 A→C→B 只要 1。

每個節點只會被確定一次，確定時掃過它的邊，所以每條邊最多鬆弛一次（無向圖兩個方向各一次）。每次鬆弛成功就 push 一筆，堆積最多 O(E) 筆，每次 push／pop 是 O(log E)，而 E ≤ V² 使得 log E ≤ 2 log V，總時間 O((V + E) log V)。空間上 dist 與 parent 是 O(V)；這裡用的是延遲刪除寫法，被更新掉的舊紀錄留在堆積裡，最壞累積到 O(E) 筆，換成支援 decrease-key 的堆積才能壓回 O(V)。不用堆積、每輪線性掃描找最小值則是 O(V²)，在 E 接近 V² 的稠密圖上反而比堆積版的 O(V² log V) 快。只問單一終點時，終點被取出的那一刻就能結束，實務上常常只看了圖的一小部分，但最壞情況仍要走完整張圖。

常見錯誤有三個。第一，沿用 BFS 的習慣在 push 時就標記已走訪：Dijkstra 的節點可能先被遠路發現、之後才被近路更新，只能在取出時確定。第二，忘了跳過舊紀錄 if d > dist[u]: continue：答案不會錯，但同一個節點會被重複展開，稠密圖上會慢很多。第三，C++ 把距離存在 int，權重一累加就溢位。怎麼和鄰近的演算法分工：邊權全是 1 用 BFS；權重只有 0 和 1 時，用雙端佇列的 0-1 BFS 就有 O(V + E)；有負權邊用 Bellman-Ford；圖是 DAG 時先拓撲排序再依序鬆弛，O(V + E) 而且負權也行；要任兩點之間的距離、而且圖不大，用 Floyd-Warshall。Prim 的最小生成樹和 Dijkstra 長得幾乎一樣，差別只在堆積裡比的是「單一條邊的權重」，而不是「從起點累加的距離」。

03演算法步驟

1. 1建鄰接串列 adj[u] = [(v, w), …]，無向圖兩個方向各加一次。確認所有權重都 ≥ 0，有負權就不能用。
2. 2dist 全部設為 ∞、parent 設為 −1；dist[src] = 0，把 (0, src) 推入最小堆積。
3. 3取出堆頂 (d, u)。若 d > dist[u]，這是被更新掉的舊紀錄，直接跳過；否則 dist[u] 在此確定。只要單一終點時，u 就是終點便可結束。
4. 4對 u 的每條邊 (v, w)：若 d + w < dist[v]，更新 dist[v] = d + w、parent[v] = u，並推入 (dist[v], v)。堆積裡 v 的舊紀錄不必刪。
5. 5重複 3–4 直到堆積為空。仍是 ∞ 的節點代表到不了；要路徑就從終點沿 parent 走到 −1，再把序列反轉。

04互動示範

六個路口 A–F 的無向圖，邊上的數字是通過那段路的分鐘數，從 A 出發，和程式碼的範例是同一張圖。節點顏色依圖例：黃色還在優先佇列裡，藍色是剛取出、正在鬆弛鄰邊的節點，處理完就變成「已確定」的實心圓。正在檢查的邊標成黃色，這次沒有更新就畫成虛線；藍色的邊是目前的最短路徑樹。留意 B：先經 A 直達記為 4，C 確定後改成 2 + 1 = 3，舊的 (4, B) 仍留在佇列裡，輪到它時被劃掉跳過。D、E 也各被改小一次；E 確定後試走 E–F，10 + 5 = 15 不比 14 短，不更新。最後一步用綠色標出 A → C → B → D → F，共 14 分鐘。

05程式碼

三個函式：延遲刪除的堆積版 Dijkstra（同時記錄 parent）、沿 parent 還原路徑，以及不用堆積、每輪掃描一遍的 O(V²) 鄰接矩陣版。兩個版本算出的距離相同，放在一起是為了對照：稀疏圖選堆積版，節點不多但邊幾乎兩兩相連時選矩陣版。

import heapq
from math import inf


def dijkstra(adj, src):
    """adj[u] = [(v, w), ...]，所有 w >= 0。回傳 (dist, parent)。O((V + E) log V)"""
    n = len(adj)
    dist = [inf] * n
    parent = [-1] * n
    dist[src] = 0
    heap = [(0, src)]                       # (目前距離, 節點)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                     # 舊紀錄：u 早就用更短的距離處理過
            continue
        # 到這裡 dist[u] 已經確定；只要單一終點，可以在這裡 if u == target: break
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:                # 鬆弛成功
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))   # 舊的紀錄不刪，取出時再跳過
    return dist, parent


def build_path(dist, parent, target):
    """沿 parent 從終點往回走，再反轉。到不了就回傳空串列"""
    if dist[target] == inf:
        return []
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]


def dijkstra_dense(mat, src):
    """鄰接矩陣版，mat[u][v] = inf 表示沒有邊。每輪線性掃描找最小，O(V²)"""
    n = len(mat)
    dist = [inf] * n
    done = [False] * n
    dist[src] = 0
    for _ in range(n):
        u = min((i for i in range(n) if not done[i]), key=lambda i: dist[i])
        if dist[u] == inf:                  # 剩下的節點都到不了
            break
        done[u] = True
        for v in range(n):
            if dist[u] + mat[u][v] < dist[v]:
                dist[v] = dist[u] + mat[u][v]
    return dist


if __name__ == "__main__":
    names = "ABCDEF"                        # 與互動示範同一張圖
    roads = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8),
             (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 5)]
    adj = [[] for _ in names]
    mat = [[inf] * len(names) for _ in names]
    for u, v, w in roads:                   # 無向圖：兩個方向各加一次
        adj[u].append((v, w))
        adj[v].append((u, w))
        mat[u][v] = mat[v][u] = w

    dist, parent = dijkstra(adj, 0)
    print(dist)                             # [0, 3, 2, 8, 10, 14]
    path = build_path(dist, parent, 5)
    print(" → ".join(names[i] for i in path))   # A → C → B → D → F
    print(dijkstra_dense(mat, 0))           # [0, 3, 2, 8, 10, 14]

06練習題

• LeetCode 743Network Delay Time（模板題：最遠節點的最短距離）Medium
• LeetCode 1514Path with Maximum Probability（機率相乘，改用最大堆積）Medium
• LeetCode 1631Path With Minimum Effort（網格上，路徑代價取最大值）Medium
• LeetCode 1976Number of Ways to Arrive at Destination（順便計數最短路徑條數）Medium
• LeetCode 2290Minimum Obstacle Removal to Reach Corner（權重只有 0 和 1，可改用 0-1 BFS）Hard
• LeetCode 2203Minimum Weighted Subgraph With the Required Paths（在反向圖上也跑一次）Hard