欢迎来到图论算法 II！

各位未来的决策数学家们，你们好！本章我们将深入探讨网络分析中两种最实用且应用广泛的算法。如果你曾经使用过导航应用或规划过配送路线，那么你实际上已经在应用我们即将学习的原理了。

别担心图论算法听起来很难——我们将一步步拆解它们。学完这一单元，你将成为寻找两点间最短路径以及覆盖每条街道最高效路径的专家！

为什么要学这个？ 这些算法是物流、交通规划和通信网络设计的核心。掌握它们，你就能高效地解决现实世界中复杂的优化问题。

第 1 节：寻找最短路径——Dijkstra 算法

1.1 什么是 Dijkstra 算法？

Dijkstra 算法（Dijkstra’s Algorithm）是一种系统性的方法，用于寻找从网络中指定的起始节点（顶点）到其他所有节点的最短距离（或最小权重）。

类比： 把 Dijkstra 算法想象成车载导航仪（SatNav）所使用的方法。它会计算出从你当前位置到每一个可能路口的行车时间，并确保在为你规划最终路线时，它已经确认该路线是绝对意义上的最短距离。

关键要求： 只有当弧的所有权重（距离、时间、成本）均为非负数（即不能为零或负数）时，该算法才能正确运行。

快速回顾：标记系统

Dijkstra 算法在每个节点 (N) 上使用两种标记：
1. 临时标记（Temporary Labels）： \( (d, P) \) —— 表示到达该节点的潜在最短距离 \(d\) 以及到达该节点的前驱节点 \(P\)。
2. 永久标记（Permanent Labels）： \( [d, P] \) —— 表示已确认的绝对最小距离 \(d\) 以及前驱节点 \(P\)。一旦标记变为永久，就不能再更改。

1.2 Dijkstra 算法的操作步骤

请仔细遵循以下步骤以确保准确性：

  1. 起始节点初始化： 给起始节点 \(S\) 添加永久标记 \( [0, -] \)（距离为零，无前驱节点）。
  2. 扫描与临时标记： 扫描最近确定的永久标记节点。
    • 观察所有尚未获得永久标记的相邻节点。
    • 计算距离：\( \text{新距离} = \text{永久标记距离} + \text{弧权重} \)。
    • 如果新距离小于该节点的当前临时标记，则用这个更短的距离更新临时标记。
  3. 固定永久标记： 在当前所有临时标记中，选择距离最小的一个。将其设为永久标记。
  4. 循环： 返回第 2 步，扫描刚刚标记为永久的那个节点。
  5. 终止： 当目标节点获得永久标记，或者所有节点都获得了永久标记（如果你需要得到到达所有节点的最短路径）时，停止运算。
如何追踪最短路径

标记 \( [d, P] \) 中的前驱节点指示符 \(P\) 至关重要。要找到完整路径，请从目标节点开始，利用前驱节点指示符回溯，直到到达起始节点。

示例： 如果目标节点 \(E\) 的永久标记为 \( [25, C] \)，这意味着最短距离是 25，且你是通过节点 \(C\) 到达的。然后查看 \(C\) 的标记，依此类推。

1.3 常见错误与技巧

记忆口诀： 记住计算顺序：Permanent（永久标记） -> Arc Weight（弧权重） -> Temporary（临时标记）（P.A.T. 拍平它！）。

避免失误（大坑！）： 在扫描节点时，必须使用它永久标记中的距离来计算新距离，而不是使用旧的临时标记。一定要始终使用已确定的最小距离作为计算基准。

考试技巧： 务必写出完整的标记 \((d, P)\) 或 \([d, P]\)。不要只写距离，因为回溯路径时需要前驱节点的信息。在替换旧的临时标记时，请清晰地划掉它们。

核心要点：Dijkstra 算法

Dijkstra 算法通过严谨的标记法，逐步确认到达每个顶点的最小距离，从而找到节点间的最短路径。其目标是求得 S 到 T 的最小距离。

第 2 节：遍历所有边——中国邮递员问题 (CPP)

2.1 什么是路径检查问题？

路径检查问题（Route Inspection Problem，通常被称为中国邮递员问题或 CPP）旨在寻找一条最短路径，要求从同一个节点出发并回到该节点，且经过网络中的每一条弧（边）至少一次。

类比： 这是邮递员送信、除雪车清理街道或垃圾车收运垃圾的完美模型——它们必须覆盖每一段街道并高效返回起点。

目标： 通过重复经过最短的弧，使路线的总长度最小化。

2.2 理解奇数点与偶数点

CPP 的关键在于识别奇数点（odd vertices）和偶数点（even vertices）。

  • 偶数点： 连出的弧数为偶数的节点。如果网络中所有节点都是偶数点，则存在一条恰好经过每条弧一次的路径（欧拉回路）。此时，解就是所有弧的权重之和。
  • 奇数点： 连出的弧数为奇数的节点。为了存在封闭路线（起点和终点相同），奇数点的数量必须总是偶数。我们必须通过重复经过某些弧来将这些奇数点“配对”，从而有效地将它们转化为偶数点。

冷知识： 这个问题之所以被称为“中国邮递员问题”，是因为它最早由中国数学家管梅谷（Mei Ko Kwan）教授于 1962 年提出并解决。

2.3 中国邮递员算法（寻找最小重复路径）

如果存在奇数点，该算法要求找到配对这些奇数点的最短方式，并重复这些最短路径。

第 1 步：找出所有奇数点

计算每个节点的度（连接的弧数）。列出所有奇数点。（奇数点的数量总会是 2、4、6 个等）。

第 2 步：找出所有可能的配对方式

如果有 \(2n\) 个奇数点，你需要列出所有可能的配对方式。

  • 示例： 如果奇数点是 A、B、C、D（四个点），则有三种可能的配对：
    1. (A 和 B) 组合，(C 和 D) 组合
    2. (A 和 C) 组合，(B 和 D) 组合
    3. (A 和 D) 组合，(B 和 C) 组合
第 3 步：计算每种配对的最短距离

对于每一组配对，找出它们之间的最短路径。必须使用网络权重（距离）来确定这些最短路径。

关键点： 如果两个奇数点之间的最短路径不是直接的一条弧，你可能需要通过观察法，甚至在该网络区域使用 Dijkstra 算法（第 1 节）来确定两点间的最小距离。

第 4 步：选择总距离最小的配对方案

计算第 2 步中每种配对方案的总距离。总距离最小的方案，即为需要重复经过的弧集。

第 5 步：计算总路径长度

最短路径的最终长度计算公式为：
\( \text{总路径长度} = (\text{网络中所有弧的权重之和}) + (\text{重复弧的最小总长度}) \)

难点情况：六个奇数点

如果你有六个奇数点（A、B、C、D、E、F），会有 15 种不同的配对方式。在考试场景中，通常只涉及 4 个或极少数情况下 6 个奇数点。处理 6 个点时，请务必系统地列出所有 15 种组合，以免漏掉最优解！

2.4 处理不同类型的图

无论图的结构如何，CPP 的原理都适用：

  • 有向图： 在 D1 课程中，我们处理的 CPP 通常是无向图。如果涉及有向图（只能单向移动），概念虽相似但复杂得多（涉及半欧拉迹），除非另有说明，否则通常超出标准 Edexcel D1 考试范围。除非另有说明，否则请假设为无向图。
  • 非平面图： 该算法适用于任何连通图，无论它是否为平面图（即能否在不发生边交叉的情况下画出）。
示例演示（四个奇数点 A, B, C, D）

假设奇数点间的最短路径为：
AB = 10, AC = 15, AD = 8, BC = 7, BD = 12, CD = 6。

比较各种配对：

  1. (AB + CD): \( 10 + 6 = 16 \)
  2. (AC + BD): \( 15 + 12 = 27 \)
  3. (AD + BC): \( 8 + 7 = 15 \)

需要重复的最小长度是 15（路径 AD 和 BC）。

核心要点：路径检查问题

CPP 用于寻找覆盖每一条弧（边）的最小距离。它需要识别奇数点，计算所有点对之间的最短路径，并找到能使重复路径总距离最小的配对组合。

结语

这些算法需要仔细且系统的工作，特别是在 Dijkstra 算法的标记过程和 CPP 的配对过程中。请使用铅笔，书写工整，并反复核对你的总数。
你现在已经掌握了解决推动现代世界的底层优化问题的工具。继续练习，你一定能完全掌握这些充满挑战的概念！