欢迎来到网络算法的世界！
在本章中，我们将探讨数学如何协助我们找出连接点与点之间，或是穿梭其间最有效率的方法。无论是 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. 建模：现实世界的问题（例如单行道或断桥）可以透过调整这些网络中的权重或方向（弧）来进行建模。
做得好！你已经掌握了现代物流与网络背后的核心逻辑。继续多练习这些算法的“演练”步骤，你会发现它们最终会变得像本能一样自然！