第三部分：路徑規劃¶

場景：封包要走哪條路最快？¶

用戶從台北連線到法蘭克福的服務。封包有多條路可以走：

路線 A：台北 → 東京 → 舊金山 → 法蘭克福（總延遲 180ms）
路線 B：台北 → 新加坡 → 孟買 → 法蘭克福（總延遲 220ms）
路線 C：台北 → 東京 → 倫敦 → 法蘭克福（總延遲 195ms）

你需要自動計算**最短路徑**，讓封包走最快的路。

「從 A 到 B，怎麼走最短？」——這是圖論中最經典的問題。

第 5 題：最短路徑計算 - Dijkstra 與 Bellman-Ford¶

(a) 問題定義與圖的表示¶

3 分 ・大二

你需要知道：如何用圖來表示網路？

題目：

將 CloudNet 網路建模為**加權有向圖**
比較兩種圖的表示方法：鄰接矩陣（Adjacency Matrix） vs 鄰接表（Adjacency List）
什麼情況下用哪種表示更好？

解答

1. 圖的建模：

頂點 \(V\)：資料中心（台北、東京、新加坡...）
邊 \(E\)：光纖連接
權重 \(w(u,v)\)：延遲（ms）

這是**加權有向圖**（可能兩個方向延遲不同）。

2. 兩種表示：

鄰接矩陣：

# adj[i][j] = 從 i 到 j 的邊權（無邊則為 ∞）
adj = [
    [0, 30, INF, INF],   # 從節點 0 出發
    [30, 0, 50, INF],    # 從節點 1 出發
    [INF, 50, 0, 20],
    [INF, INF, 20, 0]
]

鄰接表：

# adj[i] = [(鄰居, 權重), ...]
adj = {
    0: [(1, 30)],
    1: [(0, 30), (2, 50)],
    2: [(1, 50), (3, 20)],
    3: [(2, 20)]
}

3. 比較：

	鄰接矩陣	鄰接表
空間	\(O(V^2)\)	\(O(V + E)\)
查詢邊是否存在	\(O(1)\)	\(O(\text{degree})\)
遍歷鄰居	\(O(V)\)	\(O(\text{degree})\)
適合	稠密圖（\(E \approx V^2\)）	稀疏圖（\(E \ll V^2\)）

網路通常是稀疏圖（不是每兩個資料中心都直連），所以用**鄰接表**。

(b) Dijkstra 演算法¶

4 分 ・大三

你需要知道：如何找單源最短路徑？（從一個起點到所有其他點）

題目：

說明 Dijkstra 演算法的步驟
用 Priority Queue 實現 Dijkstra，分析時間複雜度

手動執行：對下圖從 S 出發

    S --1-- A
    |       |
    4       2
    |       |
    B --3-- C

提示

Dijkstra 是貪心演算法：每次選「目前距離最短」的節點擴展
關鍵性質：一旦確定某節點的最短距離，就不會再更新

解答

1. Dijkstra 步驟：

初始化：\(dist[s] = 0\)，其他 \(dist[v] = \infty\)
把 \(s\) 放入 Priority Queue
重複：
取出距離最小的節點 \(u\)
對 \(u\) 的每個鄰居 \(v\)，如果 \(dist[u] + w(u,v) < dist[v]\)，更新 \(dist[v]\)
直到 Priority Queue 為空

2. 實現：

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    pq = [(0, start)]  # (距離, 節點)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue  # 已經找到更好的路徑

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

時間複雜度： - 每個頂點最多進出 PQ 一次：\(O(V)\) 次 extract-min - 每條邊最多觸發一次 decrease-key（或 push）：\(O(E)\) 次 - 用 Binary Heap：\(O((V + E) \log V)\)

3. 手動執行：

步驟	取出	dist[A]	dist[B]	dist[C]
初始	-	∞	∞	∞
1	S	1	4	∞
2	A	1	4	3
3	C	1	4	3
4	B	1	4	3

最短距離：S→A=1, S→B=4, S→C=3

Dijkstra 正確性證明（貪心）

核心引理：當節點 \(u\) 被取出時，\(dist[u]\) 就是最終答案。

證明（反證）：假設存在更短的路徑 \(s \rightsquigarrow u'\)。

這條路徑必須經過某個「還沒確定」的節點 \(x\)。但如果 \(x\) 還沒確定，表示 \(dist[x] \geq dist[u]\)，所以 \(s \rightsquigarrow x \rightsquigarrow u'\) 的長度 \(\geq dist[u]\)。

矛盾！所以不存在更短路徑。

© 負權邊的問題¶

3 分 ・大三

某些連線提供「延遲補償」：如果走這條路，不但不加延遲，還會**減少**總延遲（負權邊）。

你需要知道：Dijkstra 能處理負權邊嗎？

題目：

舉例說明為什麼 Dijkstra **無法**處理負權邊
什麼是**負環（Negative Cycle）**？為什麼它讓最短路徑問題無解？

解答

1. 反例：

S --1-- A
 \     /
  \   /-3
   \ /
    B
    (S→B 權重 = 2)

Dijkstra 執行： - 取出 S，更新 dist[A]=1, dist[B]=2 - 取出 A，更新 dist[B] = min(2, 1+(-3)) = -2？

但 Dijkstra 會先取出 B（dist=2 < dist[A]=1？不對...）

讓我重新設計：

S --5-- A --(-3)-- B
|__________________|
        2

初始：dist[S]=0, dist[A]=∞, dist[B]=∞
取 S：dist[A]=5, dist[B]=2
取 B（dist=2 最小）：確定 dist[B]=2
取 A：dist[B] = min(2, 5-3) = 2（不更新）

但真正的最短路徑：S→A→B = 5-3 = 2，剛好相等...

更好的反例：

S --1-- A
 \       \
  2       -2
   \       \
    B-------C (B→C = 1)

Dijkstra：S→B=2 會先確定，但 S→A→C→...可能更短。

關鍵問題：Dijkstra 假設「已確定的節點不會再更新」，但負權邊打破這個假設。

2. 負環：

A --(-1)-- B
^          |
|          |
+----(-1)--+

繞一圈：\(-1 + (-1) = -2\)

如果要從 S 到 C，且路上可以繞這個環... 每繞一圈距離減 2，可以無限減！

結論：如果圖中有負環，且負環從起點可達，則「最短路徑」不存在（可以無限短）。

(d) Bellman-Ford 演算法¶

4 分 ・大三

你需要知道：如何處理負權邊（但無負環）？

題目：

說明 Bellman-Ford 演算法的步驟
分析時間複雜度
如何用 Bellman-Ford 偵測負環？

解答

1. Bellman-Ford 步驟：

def bellman_ford(graph, V, edges, start):
    dist = {v: float('inf') for v in range(V)}
    dist[start] = 0

    # 進行 V-1 輪鬆弛
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 偵測負環
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None  # 存在負環

    return dist

核心思想：最短路徑最多經過 \(V-1\) 條邊，所以做 \(V-1\) 輪「全部邊鬆弛」一定夠。

2. 時間複雜度：

\(V-1\) 輪
每輪檢查 \(E\) 條邊
總時間：\(O(VE)\)

比 Dijkstra 慢，但能處理負權邊。

3. 負環偵測：

做完 \(V-1\) 輪後，再做第 \(V\) 輪。如果還能更新任何距離 → 存在負環。

原理：如果沒有負環，\(V-1\) 輪已經收斂。還能更新表示存在「無限縮短」的可能。

Dijkstra vs Bellman-Ford

	Dijkstra	Bellman-Ford
時間	\(O((V+E)\log V)\)	\(O(VE)\)
負權邊	✗	✓
負環偵測	✗	✓
適用	無負權、效率優先	有負權、需偵測負環

(e) Floyd-Warshall：全對最短路徑¶

3 分 ・碩一

如果你需要知道**任意兩點**之間的最短路徑呢？

你需要知道：如何一次算出所有點對的最短路徑？

題目：

說明 Floyd-Warshall 演算法（DP 思路）
分析時間和空間複雜度

解答

1. Floyd-Warshall：

DP 定義：\(dp[k][i][j]\) = 從 \(i\) 到 \(j\)，只經過節點 \(\{0,1,...,k-1\}\) 的最短路徑

轉移：

\[dp[k][i][j] = \min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])\]

要麼不經過 \(k\)，要麼經過 \(k\)。

空間優化（只用 2D）：

def floyd_warshall(dist):
    V = len(dist)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

2. 複雜度：

時間：\(O(V^3)\)
空間：\(O(V^2)\)

適用場景：頂點數不多（\(V \leq 500\)），需要所有點對的答案。

進階挑戰：A* 演算法¶

3 分 ・碩一

Dijkstra 會「盲目地」向四面八方擴展。如果你知道終點的位置，能不能更聰明地搜尋？

你需要知道：如何用啟發式函數加速最短路徑搜尋？

題目：

說明 A* 演算法與 Dijkstra 的區別
什麼是**可接受啟發函數（Admissible Heuristic）**？

解答

1. A* 演算法：

Dijkstra 的優先級：\(f(v) = g(v)\)（起點到 \(v\) 的實際距離）

A* 的優先級：\(f(v) = g(v) + h(v)\)

\(g(v)\)：起點到 \(v\) 的實際距離
\(h(v)\)：啟發函數，估計 \(v\) 到終點的距離

效果：優先探索「看起來離終點近」的方向。

2. Admissible Heuristic：

定義：\(h(v) \leq\) 實際的 \(v\) 到終點距離（永不高估）

性質：如果 \(h\) 是 admissible，A* 保證找到最短路徑。

常見 heuristic： - 歐幾里德距離（直線距離） - 曼哈頓距離（格子地圖）

地理路由：如果知道每個資料中心的經緯度，可以用直線距離當 heuristic，大幅加速！

第 5 題小結：你的路徑規劃工具箱¶

「封包要走哪條路最快？」
    │
    ├─► (a) 網路怎麼建模？→ 加權圖
    │       → 鄰接矩陣 vs 鄰接表
    │
    ├─► (b) 單源最短路徑？→ Dijkstra
    │       → 貪心 + Priority Queue
    │       → O((V+E) log V)
    │
    ├─► (c) 有負權邊？→ Dijkstra 失效
    │       → 負環：無限短
    │
    ├─► (d) 處理負權邊？→ Bellman-Ford
    │       → V-1 輪鬆弛，O(VE)
    │       → 可偵測負環
    │
    ├─► (e) 所有點對最短路徑？→ Floyd-Warshall
    │       → DP，O(V³)
    │
    └─► 進階：知道終點位置？→ A*
            → 啟發式搜尋
            → Admissible heuristic 保證正確

演算法	時間	負權	適用
Dijkstra	\(O((V+E)\log V)\)	✗	無負權、單源
Bellman-Ford	\(O(VE)\)	✓	有負權、偵測負環
Floyd-Warshall	\(O(V^3)\)	✓	全對最短路徑
A*	\(O(?)\)	✗	有啟發資訊

< 上一題：流量紀錄索引 | 返回目錄 | 下一題：備援網路建設 >