跳轉到

9.2 最短路徑Dijkstra與Bellman-Ford#

概念說明#

帶權圖上，從起點 s 到其他每個點的最便宜路徑稱單源最短路徑。兩大演算法按「邊權能否為負」分工：

  • Dijkstra：邊權非負。貪心策略——「目前距離最小的點，其距離已定案，不可能再被改善」（因為繞任何其他路都只會更貴）。用最小堆積挑出定案點，效率 O((V+E) log V)。
  • Bellman-Ford：允許負權邊。對所有邊做 V−1 輪「放鬆」（relaxation），每輪至少讓一個點的距離達到最終值；之後再做一輪，若仍有邊可放鬆，代表存在負環（最短路無定義）。

「放鬆」是共通核心操作：若 dist[u] + w(u,v) < dist[v]，就更新 dist[v] 並記下前驅。

操作步驟#

Dijkstra： 1. dist[s] = 0，其餘 ∞，全部丟進（或逐步丟進）最小堆積。 2. 取出距離最小的點 u（已定案）。 3. 對 u 的每個鄰居 v 放鬆；成功則把 (新距離, v) push 進堆積。 4. 重複到堆積空。

Bellman-Ford： 1. dist[s] = 0，其餘 ∞。 2. 重複 V−1 輪：對每條邊 (u, v, w) 嘗試放鬆。 3. 第 V 輪檢查：若仍有邊可放鬆 → 有負環。

Python 實作#

import heapq

def dijkstra(graph, start):        # graph: {u: [(v, w), ...]}
    dist = {start: 0}
    pq = [(0, start)]              # (距離, 節點)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue               # 過期條目，跳過（惰性刪除）
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def dijkstra_path(graph, start, end):
    dist = {start: 0}
    prev = {}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if u == end:
            break
        if d > dist.get(u, float("inf")):
            continue
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))
    if end not in dist:
        return None, float("inf")
    path, cur = [], end
    while cur != start:
        path.append(cur)
        cur = prev[cur]
    return [start] + path[::-1], dist[end]

def bellman_ford(n, edges, start):    # edges: [(u, v, w), ...]
    dist = [float("inf")] * n
    dist[start] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:               # 提前結束
            break
    for u, v, w in edges:             # 負環檢查
        if dist[u] + w < dist[v]:
            return dist, True         # 有負環
    return dist, False

# 城市路網（里程）
roads = {
    "台北": [("台中", 160), ("花蓮", 130)],
    "台中": [("台北", 160), ("嘉義", 90)],
    "花蓮": [("台北", 130), ("台東", 190)],
    "嘉義": [("台中", 90), ("台南", 60)],
    "台東": [("花蓮", 190)],
}
d = dijkstra(roads, "台北")
print(d)      # 台北→台中→嘉義 = 250；台北→花蓮→台東 = 320
print(dijkstra_path(roads, "台北", "台東"))   # (['台北', '花蓮', '台東'], 320)

# 含負權：優惠券讓某條路變成 -50
n = 5
edges = [(0, 1, 4), (0, 2, 1), (2, 1, -2), (1, 3, 5), (2, 3, 8)]
dist, neg = bellman_ford(n, edges, 0)
print(dist, "負環:", neg)     # [0, -1, 1, 4] False

複雜度分析#

演算法 時間 負權邊 用途
Dijkstra（堆積） O((V+E) log V) ✗ 路網導航、圖論主力
Bellman-Ford O(V·E) ✓ 負權、負環偵測、分布式路由
BFS（無權圖） O(V+E) — 等權最短路，最快

練習#

  1. 在 dijkstra_path 的基礎上實作「多點直達」：回傳 start 到所有點的最短路徑樹（每點的路徑與距離）。
  2. 用 Bellman-Ford 建構匯率套利模型：把各貨幣當節點、匯率取 log 後取負當邊權，正的套利機會會以什麼形式被偵測到？
  3. 當圖是「所有邊權都是 1」時，BFS 比 Dijkstra 快且不用堆積。寫一個通用函式：邊權全等於 1 時自動改用 BFS，否則用 Dijkstra。