歡迎來到網絡算法的世界！
在本章中，我們將探討數學如何協助我們找出連接點與點之間，或是穿梭其間最有效率的方法。無論是 Google 地圖為你找出前往朋友家最快的路徑，還是公用事業公司以最低成本鋪設光纖網絡，網絡算法 (Network Algorithms) 都在背後默默運作。這是你 OCR 進階數學課程中離散數學 (Discrete Mathematics) 的一部分。
如果剛開始覺得步驟繁複，請不用擔心。你可以把這些算法想像成食譜：只要按部就班地跟隨指示，你每次都能得到正確的結果！
1. Dijkstra 算法：尋找最短路徑
想像你現在身處家中（頂點 A），想要前往電影院（頂點 G）。中間有許多不同的道路和交叉路口。Dijkstra 算法就是我們用來找出兩個特定頂點之間最小權重路徑 (least weight path)（即最短距離、最低成本或最快時間）的工具。
運作方式（「按部就班」的食譜）
1. 從起點出發：將你的起始頂點標記為距離 0。這就是它的永久標籤 (permanent label)。
2. 觀察鄰居：對於連接到當前頂點的每一個頂點，將邊的權重加上當前頂點的永久標籤，計算出一個暫時標籤 (temporary label)。
3. 更新標籤：如果新計算出的距離小於之前的暫時標籤，就更新它。如果沒有，則保持原樣。
4. 永久化：觀察網絡中所有的暫時標籤，挑選數值最小的一個並將其永久化。現在這就是你的「當前」頂點。
5. 重複：持續此過程，直到目的地頂點獲得永久標籤為止。
6. 回溯：要找出實際路徑，請從目的地開始向後推算，挑選那些永久標籤之差等於邊權重的邊。
記憶小貼士：衛星導航法則
Dijkstra 算法就像一個貪婪的衛星導航。它總是尋找下一步可行的絕對最短距離，確保當你到達終點時，你已經走了最有效率的路徑。
複雜度與效率
在考試中，你需要知道 Dijkstra 算法具有二次階複雜度 (quadratic order)。在「大 O 符號 (Big O notation)」中，寫作 \(O(n^2)\)，其中 \(n\) 是頂點的數量。這意味著如果你將頂點數量加倍，運算所需的時間大約會增加為原來的四倍！
快速回顧：Dijkstra 用於尋找兩個特定點之間的最短路徑。
2. 最小生成樹 (Minimum Spanning Trees, MST)
有時候，我們並非只想從 A 到 B；我們是想用最低的成本連接網絡中的每一個點。這就是所謂的最小生成樹。
重要術語：樹 (Tree) 是指沒有循環（即沒有環路）的圖。生成樹 (Spanning Tree) 則連接了圖中的所有頂點。
Kruskal 算法
如果你手邊有一份所有邊的列表，Kruskal 算法通常是手動計算最簡單的方法。它就像鋪設鐵路系統一樣，先購買最便宜的軌道，不管它們在圖上的位置如何。
1. 排序：將所有邊按權重從最小到最大排列。
2. 選擇：選擇權重最小的邊。
3. 檢查循環：將該邊加入你的樹中，除非它會造成循環（環路）。如果會產生環路，就捨棄它！
4. 重複：持續選擇下一個最小的邊，直到所有頂點都連接起來。
Prim 算法
Prim 算法則不同，它是從一個起始點開始「生長」出樹。你可以透過圖解法或使用距離矩陣 (distance matrix) 來完成。
圖解法：
1. 隨意挑選一個頂點作為起點。
2. 觀察所有連接到「已生長」樹與「新」頂點的邊。挑選其中最短的一條。
3. 重複此步驟，直到所有頂點都被包含進來！
矩陣法 (表格法)：
1. 挑選一個起始列（通常是 A）並刪除該列。
2. 在 A 列標上「1」。
3. 觀察已標記列中的所有數字，圈選出最小的可用數值。
4. 該數值所在的列告訴你下一個要加入的頂點。為其所在的列標上下一個數字（2, 3 等等）並刪除該行。
5. 重複此過程，直到所有頂點都被標記。
你知道嗎？
雖然 Kruskal 和 Prim 算法看起來不同，但它們最終得到的最小總權重總是相同的！
複雜度與效率
Prim 和 Kruskal 算法皆具有三次階複雜度 (cubic order)，寫作 \(O(n^3)\)。當網絡變得非常大時，電腦處理它們會比處理 Dijkstra 算法稍顯「吃力」。
重點總結：當你需要以最低成本連接所有事物時（例如電力網），請使用 Prim 或 Kruskal 算法。
3. 選擇正確的算法
進階數學中常見的挑戰，是如何決定該使用哪種「工具」來解決問題。以下是簡易指南：
如果出現以下情況，請使用 Dijkstra...
- 題目要求找出從 A 到 B 的「最短路線」。
- 你需要找出兩個特定地點之間的「最小時間」或「最低成本」。
如果出現以下情況，請使用 Prim 或 Kruskal...
- 題目要求找出「最小連接器」。
- 你需要「連結所有頂點」，以便任兩點之間都有路徑可通。
- 你想求得網絡的「最小總長度」。
常見陷阱：
1. Kruskal 算法中的循環：學生經常忘記檢查邊是否會形成環路。如果你能不走回頭路就從 A 回到 A，那你就是製造了一個循環！請停止並拒絕該邊。
2. 更新 Dijkstra：在計算暫時標籤時，一定要將邊權重加到你剛離開的頂點的永久標籤上，而不是加到之前的暫時標籤上。
3. 矩陣法：在使用 Prim 的矩陣法時，記得要刪除你剛加入樹中頂點的那一列，以免不小心重複選取它。
章節總結
1. Dijkstra 算法：找出兩點之間的最短路徑。其複雜度為 \(O(n^2)\)（二次階）。
2. Kruskal 算法：透過挑選最小的邊並避開循環來找出最小生成樹。其複雜度為 \(O(n^3)\)（三次階）。
3. Prim 算法：從起始頂點開始生長來找出最小生成樹。可用於圖形或矩陣。其複雜度為 \(O(n^3)\)（三次階）。
4. 建模：現實世界的問題（例如單行道或斷橋）可以透過調整這些網絡中的權重或方向（弧）來進行建模。
做得好！你已經掌握了現代物流與網絡背後的核心邏輯。繼續多練習這些算法的「演練」步驟，你會發現它們最終會變得像本能一樣自然！