欢迎来到图算法 II：寻找最短路径！
你好，未来的数学家们！本章内容非常实用且强大。在决策数学 1 (D1) 中，我们将从单纯的画图进阶到真正“使用”图论来解决现实世界中的问题。
本节的主要重点是找到两点之间，或者在某些情况下，一点到*所有其他点*之间的最短路径。你可以把这看作是 GPS 导航系统背后的数学原理！
单元 D1 重点：最短路径问题
我们经常处理赋权图 (weighted graphs)，其中每条弧（或边）都有一个数值（即权重），代表距离、时间、成本或容量。我们的首要目标是使路径上的总权重最小化。
你知道吗？ 寻找最短路径在物流、电信（数据包路由）甚至优化工厂内部动线方面都至关重要。
Dijkstra 算法：最短路径发现者
解决最短路径问题（当权重为非负时）最著名且最可靠的方法是迪杰斯特拉算法 (Dijkstra's Algorithm)。它是从一个起始节点 (source) 到图中每一个其他节点寻找最短路径的高效方法。
预备检查：为什么要用 Dijkstra 算法？
- 它保证能找到最短路径。
- 它只能用于所有权重（距离/时间）均为非负（零或正数）的图中。
类比： 想象你是一名从仓库（节点 S）出发的邮递员。Dijkstra 算法是你系统化工作的方式，确保你每次前往一个新的区域时，走的都是到达该区域最快或最短的路线。
核心概念：标记，标记，还是标记！
Dijkstra 算法的工作原理是为每个节点分配标签。每个标签由两部分组成：
标签符号： \( (L, P) \)
- L (长度/数值)： 从起始节点到该节点的当前已知最短距离。
- P (前驱节点)： 在目前已找到的最短路径中，紧接在该节点之前的那个节点。
这些标签存在两种状态：临时 (Temporary) 或 永久 (Permanent)。
- 临时标签： 这是目前对最短路径长度的最佳猜测。如果发现更短的路线，它可以被划掉并更新。
- 永久标签： 一旦我们确定当前的长度 L 绝对是到达该节点的最短距离，该标签就会变为永久（通常通过给标签加框来表示）。该节点此时已确定，我们将其作为计算到达其他临时节点路径的基础。
记忆小贴士： 想想 Permanent（永久）的首字母 'P'。一旦路径成为永久的，你就承诺 (Promise) 不会再改变它！
Dijkstra 算法分步指南
如果起初觉得有些复杂，不要担心。这是一个机械化的过程。如果你能系统地按照这些步骤操作，你一定会成功！
第 1 步：初始化
- 将起始节点（源节点，S）的标签设为永久： \( \mathbf{(0, -)} \)。(长度为 0，没有前驱节点)。
- 将所有其他节点的标签设为临时，通常记为 \( (\infty, -) \)，或者最初留空即可。
第 2 步：扫描永久节点
- 识别最近确定的永久标签节点（我们称之为节点 X）。
- 查看所有直接与节点 X 相连的临时节点。
-
使用以下公式计算到每个相邻临时节点 (Y) 的潜在新长度：
到 Y 的潜在长度 = (X 的永久长度) + (弧 X 到 Y 的权重)
第 3 步：更新临时标签（扫描）
- 对于每个临时节点 (Y)，将其潜在新长度（第 2 步中计算出的值）与它当前的临时长度进行比较。
- 如果潜在新长度小于当前长度，则划掉旧的临时标签，并写下新的、优化后的标签 \( (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 被赋予了永久标签，你就可以停止该过程。没必要将剩下的临时节点也全部永久化，这样在考试中可以节省时间！
关于替代算法（旅行商问题 - 界限）的说明
虽然 Dijkstra 算法解决了单一源点的最短路径问题，但你可能会遇到与旅行商问题 (TSP) 相关的问题，它要求找到访问每个节点恰好一次并回到起点的最短回路。
D1 课程不要求你解出 TSP，因为它在计算上非常困难。相反，你需要能够找到解的界限 (bounds)：
TSP 的下界 (Lower Bound)
在 D1 中寻找下界的标准方法包含两个关键步骤：
- 移除一个节点（例如节点 A）： 移除节点 A 后，使用普里姆算法 (Prim’s) 或克鲁斯卡尔算法 (Kruskal’s)（在算法 I 中已涉及）找到剩余图的最小生成树 (MST)。
- 重新连接最短路径： 将最初将节点 A 连接到其余部分的两个最短弧加回来。
- 下界计算： 下界 = MST 权重 + 连接回 A 的两条最短边之和。
实际的 TSP 解一定大于或等于此下界。
TSP 的上界 (Upper Bound)（最近邻算法）
寻找上界（一种可能的，但不保证是最短的回路）最简单的方法通常是使用最近邻算法 (Nearest Neighbour Algorithm)。
- 从给定的节点 (S) 出发。
- 移动到最近的未访问节点。
- 重复第 2 步，直到所有节点都被访问过。
- 直接返回起始节点 (S)。
实际的 TSP 解一定小于或等于此上界。
关键区别： Dijkstra 算法找到的是两点间的最短路线；而 TSP 找到的是访问所有点的最短闭合回路。它们是使用不同技术解决的不同问题。
恭喜你！你已经掌握了决策数学中路由和路径查找的核心算法。继续练习那些标签更新，你会发现这些题目非常简单明了！