歡迎來到圖論算法 II！

各位未來 Decision Mathematics 的高手們，你們好！本章節將深入探討網絡分析中最實用、應用最廣泛的兩種算法。如果你曾使用過導航 App 或規劃過送貨路線，其實你已經用上了我們即將學習的原理。

如果以前覺得圖論算法很難，請不用擔心——我們會把它們拆解成簡單的步驟。學完這一章，你將成為「兩點間最短路徑」及「最高效覆蓋所有街道」規劃的大師！

為什麼這很重要？ 這些算法是物流、交通規劃和通訊網絡設計的核心。掌握它們，就能確保你能高效地解決複雜的現實優化問題。

第一節：尋找最短路徑 – Dijkstra 算法

1.1 什麼是 Dijkstra 算法？

Dijkstra 算法是一種系統性方法，用於找出從指定的起始節點（頂點）到網絡中所有其他節點的最短距離（或最小權重）。

類比： 把 Dijkstra 算法想像成衛星導航（SatNav）所使用的方法。它會計算從你當前位置到每一個可能路口的「最快路線」，並確保當它告訴你最終路線時，它已經徹底驗證該路線確實是絕對的最短距離。

關鍵要求： 只有當所有弧（arc）的權重（距離、時間、成本）均為非負數（即不能為零或負數）時，該算法才能正確運作。

快速複習：標記系統

Dijkstra 算法在每個節點 (N) 使用兩種類型的標記：
1. 臨時標記 (Temporary Labels)： \( (d, P) \) - 代表一個潛在的最短距離 \(d\) 以及到達該點的前一個節點 \(P\)。
2. 永久標記 (Permanent Labels)： \( [d, P] \) - 代表已確認的絕對最小距離 \(d\) 以及前一個節點 \(P\)。一旦標記變為永久，就不可更改。

1.2 Dijkstra 算法的操作步驟

請仔細按照以下步驟，以確保準確性：

  1. 起始節點初始化： 將起始節點 \(S\) 標記為永久標記 \( [0, -] \)（距離為零，無前一個節點）。
  2. 掃描與臨時標記： 掃描最近確定的永久標記節點。
    • 查看所有尚未擁有永久標記的相鄰節點。
    • 計算距離：\( \text{新距離} = \text{永久標記距離} + \text{弧權重} \)。
    • 如果新計算的距離小於該節點現有的臨時標記，則將其替換為這個更短的數值。
  3. 將標記轉為永久： 在所有現有的臨時標記中，選擇距離最小的一個，將其設為永久標記。
  4. 重複： 返回步驟 2，掃描剛剛設為永久標記的節點。
  5. 結束： 當目的地節點獲得永久標記，或所有節點都已完成永久標記（如果你需要到所有節點的最短路徑）時，即可停止。
如何追蹤最短路徑

標記 \( [d, P] \) 中的前一個節點指示器 \(P\) 至關重要。若要找出路徑，請從目的地節點開始，利用前一個節點指示器向回推導，直到到達起始節點為止。

例子： 如果目的地節點 \(E\) 的永久標記為 \( [25, C] \)，這意味著最短距離是 25，且你是經由節點 \(C\) 到達的。接著，你再檢查 \(C\) 的標記，依此類推。

1.3 常見錯誤與貼士

記憶小撇步： 記住計算順序：Permanent（永久） -> Arc Weight（弧權重） -> Temporary（臨時）（簡稱 P.A.T.！）。

必避錯誤（大陷阱！）： 掃描節點時，務必使用該節點的永久標記距離來計算新距離，千萬別用舊的臨時標記。請始終使用已確認的最小距離作為你的起點。

考試貼士： 永遠寫出完整的標記 \((d, P)\) 或 \([d, P]\)。不要只寫數字，因為你需要前一個節點指示器來回溯路徑。當替換臨時標記時，記得清晰地劃掉舊值。

核心總結：Dijkstra 算法

Dijkstra 算法通過嚴謹的標記法，逐步確認到每個頂點的最小距離，從而找到節點間的最短路徑。目標是得出從 S 到 T 的最小距離。

第二節：遍歷所有邊 – 中國郵差問題 (CPP)

2.1 什麼是路徑檢查問題 (Route Inspection Problem)？

路徑檢查問題（通常稱為中國郵差問題或 CPP）旨在找出從同一個節點出發並回到該點，且至少經過網絡中每一條弧（邊）一次的最短路徑。

類比： 這是郵差派信、剷雪車清掃街道或垃圾車收集垃圾的完美模型——他們必須走遍每一段街道並高效地回到起點。

目標： 通過重複走最短的弧，使總路線長度最小化。

2.2 理解奇數和偶數頂點

CPP 的關鍵在於識別奇數點和偶數點。

  • 偶數頂點 (Even Vertex)： 連接了偶數條弧的節點。如果網絡中所有節點都是偶數點，那麼存在一條正好經過每條弧一次的路徑（即歐拉迴路 Eulerian circuit）。此時解法僅是所有弧權重的總和。
  • 奇數頂點 (Odd Vertex)： 連接了奇數條弧的節點。為了存在一條封閉路徑（起點和終點相同），網絡中的奇數點數量必須是偶數個。我們必須重複走某些弧來「配對」這些奇數點，有效地將它們變為偶數點。

你知道嗎？ 這個問題被稱為中國郵差問題，是因為它最早由中國數學家管梅谷（Mei Ko Kwan）於 1962 年提出並解決。

2.3 中國郵差算法（尋找最小重複路徑）

如果存在奇數點，算法就需要找出將它們兩兩配對的最短路徑，並重複這些路徑。

步驟 1：找出所有奇數頂點

計算連接每個節點的度數（弧的數量），列出所有奇數頂點。（它們的數量永遠會是 2、4、6 等偶數個）。

步驟 2：找出所有可能的配對方案

如果你有 \(2n\) 個奇數點，你需要列出所有可能的兩兩配對方式。

  • 例子： 如果奇數點是 A、B、C、D（共四個），你有三種配對可能：
    1. (A 和 B) 與 (C 和 D) 配對
    2. (A 和 C) 與 (B 和 D) 配對
    3. (A 和 D) 與 (B 和 C) 配對
步驟 3：計算每對配對的最短距離

對於每對奇數頂點，找出它們之間的最短路徑。你必須使用網絡權重（距離）來確定這些最短路徑。

關鍵點： 如果兩點間的最短路徑不是一條直接的弧，你可能需要使用觀察法，甚至在該網絡區域內使用 Dijkstra 算法（見第一節）來確認兩點間的最小距離。

步驟 4：選擇總距離最小的配對

將步驟 2 中每一種配對組合的距離加總。總距離最小的那個組合，就是必須重複走的弧。

步驟 5：計算總路線長度

最短路徑的最終長度計算如下：
\( \text{總路線長度} = (\text{網絡中所有弧權重之和}) + (\text{重複弧的最小總長度}) \)

困難情況：六個奇數頂點

如果你有六個奇數頂點（A、B、C、D、E、F），會有 15 種不同的配對方式。在考試中，通常只會考到 4 個，偶爾會考 6 個。處理 6 個點時，請務必系統性地列出所有 15 種配對，以免遺漏掉最佳方案！

2.4 處理不同類型的圖

CPP 原理適用於任何圖結構：

  • 有向圖 (Directed Graphs)： 在 D1 課程中，我們通常處理無向圖的 CPP。如果是處理有向圖（即只能單向行駛），概念類似但複雜得多（涉及半歐拉路徑），這通常超出標準 Edexcel D1 的考試範圍，除非題目另有說明。請默認圖為無向圖。
  • 非平面圖 (Non-Planar Graphs)： 該算法適用於任何連通圖，無論它是否為平面圖（即邊與邊是否交叉）。
例子示範（四個奇數頂點 A、B、C、D）

假設奇數點間的最短路徑為：
AB = 10, AC = 15, AD = 8, BC = 7, BD = 12, CD = 6。

我們比較配對：

  1. (AB + CD): \( 10 + 6 = 16 \)
  2. (AC + BD): \( 15 + 12 = 27 \)
  3. (AD + BC): \( 8 + 7 = 15 \)

因此，最小的重複長度為 15（路徑 AD 和 BC）。

核心總結：路徑檢查問題

CPP 用於尋找覆蓋每一條弧的最短距離。它需要識別奇數點、計算各點間的最短路徑，並找出能使重複距離總和最小的配對組合。

結語與鼓勵

這些算法需要細心且系統化的操作，特別是在 Dijkstra 算法的標記過程和 CPP 的配對過程中。請準備鉛筆、保持整潔，並反覆核對總數。
你現在已掌握了驅動現代世界運作的基礎優化問題解決工具。繼續練習，你一定能熟練掌握這些極具挑戰性的概念！