欢迎来到最优化算法！
你好！你有没有想过 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、互联网路由与物流规划。
如果一开始觉得有点难也不要紧！掌握戴克斯特拉算法的最佳方法，就是拿出一张纸，画几个带有数字的圆圈和线条，然后尝试自己追踪步骤。你很快就能熟练上手！