歡迎來到最佳化演算法！
你好！你有沒有想過 Google 地圖是如何在交通繁忙的尖峰時刻，神奇地幫你找出回家的最短路徑？或者數據封包是如何穿過龐大的網際網路迷宮，準確地到達你的電腦？
在這個章節中，我們將深入探討最佳化演算法 (Optimisation Algorithms)。具體來說，我們會研究戴克斯特拉演算法 (Dijkstra’s Shortest Path Algorithm)。「最佳化」簡單來說，就是找出執行某項任務的「最佳」或「最高效率」的方法。在電腦科學中，這通常意味著找出最短距離、最低成本或最快時間。
如果一開始覺得有點深奧也不用擔心，我們會透過簡單的類比，將這些概念拆解成一步步的步驟！
先備知識：什麼是圖 (Graph)？
在開始之前，請記住戴克斯特拉演算法是運作在加權圖 (Weighted Graph) 上的。
1. 節點 (Nodes 或 Vertices)： 地圖上的「站點」或點（例如城市或路由器）。
2. 邊 (Edges 或 Arcs)： 連接這些站點的路徑（例如道路或網路電纜）。
3. 權重 (Weights)： 邊上的數值，代表路徑的「成本」（例如距離、時間或金錢）。
戴克斯特拉最短路徑演算法
戴克斯特拉演算法是一種著名的演算法，用於找出加權圖中從一個特定的起始節點到所有其他節點的最短路徑。
試著這樣想：你站在一個「起點」節點，想要到達「目的地」節點。演算法會循序漸進地探索路徑，並始終記錄下目前為止到達地圖上每一個「站點」的最短距離。
生活化類比：踏腳石
想像你正試圖踩著踏腳石過池塘。每塊石頭上都有一個數字，代表它的「濕滑程度」（權重）。你的目標是用最低的總濕滑分數到達對岸。
戴克斯特拉演算法就像一個非常謹慎的人：他會查看從目前位置所能觸及的所有石頭，記錄下到達那裡所需的總濕滑值，然後始終選擇目前累積總分最低的那塊石頭移動。如果他在過程中發現了到達某塊石頭的更好路徑，他會隨時更新他的筆記。
演算法運作方式（追蹤邏輯）
AQA 課程大綱不需要你背誦精確的程式碼，但你必須具備追蹤 (Trace) 演算法的能力（即一步步模擬其過程）。以下是其邏輯流程：
1. 初始化：
- 給每個節點分配一個距離值。將起點 (Start Node) 設為 0，所有其他節點設為無限大 \( (\infty) \)**。
- 將所有節點標記為未訪問 (unvisited)。
2. 迴圈：
- 選擇一個距離最小的未訪問節點，我們稱之為「當前節點 (Current Node)」。
- 對於當前節點，查看它所有未訪問的鄰居。
- 計算透過當前節點到達這些鄰居的距離。
- 如果這個新距離小於該鄰居目前記錄的距離，就更新它！
3. 結束步驟：
- 當你檢查完當前節點的所有鄰居後，將當前節點標記為已訪問 (visited)。已訪問的節點將不再被檢查。
- 重複上述迴圈，直到所有節點都被訪問（或到達你的目標）。
快速回顧：為什麼要用無限大？
我們將初始距離設為無限大，是因為我們還不知道路徑！這相當於在說：「我還沒找到到達這裡的路，所以任何我之後找到的路，肯定都比現在這個『無限大』更好。」
追蹤戴克斯特拉：簡單範例
想像一個圖包含節點 A、B 和 C。
- 邊 A 到 B 的權重為 5。
- 邊 B 到 C 的權重為 2。
- 邊 A 到 C 的權重為 10。
如果我們從 A 開始：
1. 步驟 1： 起點 A = 0，B = \( \infty \)，C = \( \infty \)。
2. 步驟 2： 未訪問節點中最小的是 A。鄰居有 B（距離 5）和 C（距離 10）。兩者都小於 \( \infty \)，因此我們更新它們。
- 距離：A=0, B=5, C=10。 將 A 標記為已訪問。
3. 步驟 3： 未訪問節點中最小的是 B (5)。它的鄰居是 C。
- 透過 B 到達 C 的距離是 \( 5 + 2 = 7 \)。
- 7 是否小於 C 目前的距離 (10)？是的！ 將 C 更新為 7。
- 距離：A=0, B=5, C=7。 將 B 標記為已訪問。
4. 步驟 4： 只剩下 C，將其標記為已訪問。A 到 C 的最短路徑為 7。
重點總結：
戴克斯特拉演算法是一種「貪婪 (greedy)」演算法——在每一步中，它都選擇當下看起來最好的選項（距離最小），以確保在結束時能找出數學上完美的最短路徑。
最短路徑演算法的應用
在考試中，你可能會被問到這些演算法的實際用途。以下是幾個主要應用：
1. 衛星導航系統 (GPS)： 在兩個地點之間找出開車距離最短或時間最快的路徑。
2. 網路路由 (Network Routing)： 在網際網路上，路由器使用類似戴克斯特拉的演算法來找出傳送數據封包到目的地最快的方式。
3. 社群網路： 透過尋找用戶之間連結的最短路徑，來建議「你可能認識的人」。
4. 物流規劃： 為航空公司規劃航線，或為快遞公司規劃配送路線，以節省燃油和時間。
你知道嗎？
創造這個演算法的電腦科學家艾茲格·戴克斯特拉 (Edsger Dijkstra)，據說是在與未婚妻在咖啡館喝咖啡時，只花了 20 分鐘就構思出了這個演算法！他當時沒有使用紙筆，完全是在腦中思考完成的，因為他想證明這個問題其實可以很簡單。
常見錯誤：請避免！
- 忘記加上權重： 更新鄰居節點距離時，記得必須加上當前節點的距離**與邊的權重**。不要只看邊的權重！
- 選錯下一個訪問的節點： 務必選擇從起點開始總距離最小**的那個節點，而不是隨便選一個鄰居。
- 更新成較大的數字： 只有當你找到的新路徑比原本記錄的更短**時，才更新節點的距離。
章節摘要
最佳化 (Optimisation)： 讓演算法儘可能有效率（例如找出最短路徑）。
戴克斯特拉演算法 (Dijkstra’s Algorithm)： 找出從起點到加權圖中所有其他節點的最短路徑。
貪婪策略 (Greedy approach)： 總是選擇「成本最低」的未訪問節點來進行下一步探索。
現實應用： GPS、網際網路路由與物流規劃。
如果一開始覺得有點難也不要緊！掌握戴克斯特拉演算法的最佳方法，就是拿出一張紙，畫幾個帶有數字的圓圈和線條，然後嘗試自己追蹤步驟。你很快就能熟練上手！