歡迎來到圖論演算法 II：尋找最短路徑！
各位未來的數學家，大家好！這一章內容非常實用且強大。在決策數學 1 (D1) 中，我們將從單純的繪製圖形，進階到真正「使用」這些圖形來解決現實生活中的問題。
本節的重點在於尋找兩點之間，甚至是某一點到「所有其他點」之間的最短路徑。你可以將其視為 GPS 導航系統背後的數學原理！
單元 D1 重點：最短路徑問題
我們經常處理加權圖 (weighted graphs)，其中每條弧（或邊）都有一個數值（即權重），代表距離、時間、成本或容量。我們的主要目標是使路徑上的總權重最小化。
你知道嗎？ 尋找最短路徑在物流、電信（數據包路由），甚至優化工廠車間動線方面都至關重要。
Dijkstra 演算法：最短路徑搜尋器
解決最短路徑問題（當權重為非負數時）最著名且可靠的方法是 Dijkstra 演算法。它是一種高效的方法，用於找到從起始節點（源點）到圖中每個其他節點的最短路徑。
先備知識檢查：為什麼選用 Dijkstra？
- 它保證能找到最短路徑。
- 它只能應用於所有權重（距離/時間）均為非負數（零或正數）的圖中。
類比： 想像你是一名從郵局（節點 S）出發的郵差。Dijkstra 演算法是你的一套系統化方法，確保每次前往新區域時，你都選擇了到達該處最快或最短的路徑。
關鍵概念：標籤，標籤，還是標籤！
Dijkstra 演算法透過為每個節點分配標籤來運作。每個標籤由兩部分組成：
標籤記號： \( (L, P) \)
- L (長度/數值 - Length): 從起始節點到該節點目前已知的最短距離。
- P (前驅節點 - Preceding Node): 在目前找到的最短路徑上，緊接在該節點之前的節點。
這些標籤存在兩種狀態：暫時 (Temporary) 或 永久 (Permanent)。
- 暫時標籤： 這是目前對最短路徑長度的「最佳猜測」。如果發現了更短的路徑，它可以被劃掉並更新。
- 永久標籤： 一旦我們確定目前的長度 L 絕對是到達該節點的最短距離，該標籤就會變成永久（通常透過在標籤外畫一個方框來表示）。此節點現在已確定，我們將以它為基礎來計算到其他暫時節點的路徑。
記憶小撇步： 記住「永久」(Permanent) 的「P」。一旦路徑變成永久，你就要 Promise (承諾) 不再改變它！
Dijkstra 演算法逐步指南
如果一開始覺得有點複雜，別擔心，這是一個機械化的過程。只要系統地遵循這些步驟，你就一定會成功！
步驟 1：初始化
- 將起始節點（源點，S）的標籤設為永久： \( \mathbf{(0, -)} \)。(長度為 0，無前驅節點)。
- 將所有其他節點的標籤設為暫時，通常記作 \( (\infty, -) \)，或者一開始先留空即可。
步驟 2：掃描永久節點
- 找出最近一個被標記為永久的節點（我們稱之為節點 X）。
- 查看所有直接與節點 X 相連的暫時節點。
-
使用以下公式計算到每個相鄰暫時節點 (Y) 的潛在新長度：
到 Y 的潛在新長度 = (X 的永久長度) + (從 X 到 Y 的弧權重)
步驟 3：更新暫時標籤（掃描）
- 對於每個暫時節點 (Y)，將計算出的潛在新長度與其目前的暫時長度進行比較。
- 如果潛在新長度小於目前的長度，請劃掉舊的暫時標籤，並寫上新的、改進後的標籤 \( (L_{new}, X) \)。
常見錯誤提醒： 學生經常忘記劃掉舊的暫時標籤。如果你發現了更短的路徑，務必更新標籤！
步驟 4：將標籤設為永久
- 一旦掃描完節點 X 並更新了所有相鄰的暫時標籤後，查看圖中所有目前的暫時標籤。
- 選擇長度 (L) 最小的那個暫時標籤。
- 將此標籤設為永久（畫上框）。該節點現在成為下一次迭代（回到步驟 2）的新的節點 X。
步驟 5：停止條件
- 重複步驟 2、3 和 4，直到所有節點都被設為永久標籤。
追溯最短路徑
演算法完成後，到任何節點的最短距離就是其永久標籤中的長度 (L)。但該如何找到實際的路徑呢？
你需要使用標籤中的前驅節點 (P) 並從後往前追溯！
- 從終點節點 (T) 開始。
- 查看它的永久標籤 \( (L_T, P_T) \)。最短路徑是直接從節點 \( P_T \) 過來的。
- 移動到節點 \( P_T \)。查看它的標籤，找到前一個節點。
- 繼續逐個節點向後追溯，直到到達起始節點 (S)。
- 按正確的正向順序（從 S 到 T）寫出路徑。
範例：如果節點 F 的最終標籤是 \((15, C)\)，代表路徑是從 C 來的。如果 C 的標籤是 \((10, B)\)，代表路徑是從 B 來的。目前追溯到的路徑片段是 S → ... → B → C → F。
快速複習：Dijkstra 的檢查點
重點 1：永久方框
一旦一個標籤被畫上方框（設為永久），其長度 (L) 就是從起點到該點確定的最短距離。這個距離永遠不會再改變。
重點 2：關鍵選擇
在步驟 4 決定將哪個暫時標籤變為永久時，你必須查看圖上所有的暫時標籤，而不僅僅是剛才掃描的那個節點相鄰的節點。
重點 3：路徑記錄
務必使用前驅節點 (P) 從後往前記錄路徑，然後在最終答案中以正向呈現。
替代場景：尋找兩個特定節點之間的最短路徑
有時考試只要求尋找節點 A 和節點 B 之間的最短路徑（而非從 A 到所有節點）。
你依然使用 Dijkstra 演算法，但一旦節點 B 的標籤變成永久，你就可以停止過程。無需將剩餘的暫時節點變為永久，這樣可以在考試中節省時間！
關於替代演算法的說明（TSP - 界限）
雖然 Dijkstra 解決了單源最短路徑問題，但你可能會遇到與旅行推銷員問題 (TSP) 相關的問題，該問題要求找到訪問每個節點且僅訪問一次，最後回到起點的最短路徑（迴路）。
D1 課程不要求你解出 TSP，因為它的計算難度很高。相反，你需要具備尋找解的界限 (bounds) 的能力：
TSP 的下界 (Lower Bound)
在 D1 中尋找下界的標準方法包含兩個關鍵步驟：
- 移除一個節點（例如節點 A）： 移除節點 A 後，使用 Prim 演算法或 Kruskal 演算法（在演算法 I 中介紹過）找出剩餘圖形的最小生成樹 (MST)。
- 重新連接最短的邊： 將原先連接節點 A 到其餘圖形的兩條最短弧加回來。
- 下界計算： 下界 = MST 權重 + 連接回 A 的兩條最短邊之和。
實際的 TSP 解必須大於或等於此下界。
TSP 的上界 (Upper Bound)（最近鄰居法）
尋找上界（一種可能但不保證是最短的巡迴路徑）最簡單的方法通常是使用最近鄰居演算法 (Nearest Neighbour Algorithm)。
- 從給定的節點 (S) 開始。
- 移動到最近的未訪問節點。
- 重複步驟 2，直到所有節點都被訪問過。
- 直接回到起始節點 (S)。
實際的 TSP 解必須小於或等於此上界。
關鍵區別： Dijkstra 找到的是兩點之間的最短路徑。TSP 找到的是訪問所有點的最短完整迴路。它們是不同的問題，使用不同的技術來解決。
恭喜你！你已經掌握了決策數學中路由和路徑搜尋的核心演算法。繼續練習那些標籤更新，你會發現這些題目其實非常直接！