8.2 最短路径
(Shortest Paths)

本节中，我们研究这样一个问题: 在一组互不相交的多边形障碍物的环境中，寻找两个给定点 \(s\) 和 \(t\) 之间的最短路径，这些多边形总共有 \(n\) 个顶点。 图 8.1 展示了一个示例: 路径 \(A\) 比路径 \(B\) 更短，并且实际上是连接 \(s\) 和 \(t\)，且避开所有障碍物内部的唯一最短路径。 假设 \(s\) 和 \(t\) 不在任何多边形的内部。这与障碍物互不相交的假设结合，意味着始终存在至少一条可行路径。因此问题的核心是找到最优的那条路径。

8.2.1. 可见图 (Visibility Graphs)

\(s\) 和 \(t\) 之间确实存在无限多条路径，对这种无限的可能性集合进行优化时，通常的第一步是将搜索空间缩减为有限的、可数的候选对象。 在这个例子中，实现这一点的依据是: 最短路径由若干线段组成，这些线段的端点要么是 \(s\)、\(t\)，要么是多边形的顶点。 既然 \(s\) 和 \(t\) 在这个意义上"表现得像"多边形顶点，那么将 \(s\) 和 \(t\) 视为各有一个顶点的点多边形，讨论就会简化。于是，上述观察结果就可以形式化为如下引理:

我们曾在第 6 章(6.1 节)中提到过可见图。 一组多边形的可见图 visibility graph，其节点对应于多边形的顶点，其边对应于能够互相看见的顶点 \(x\) 和 \(y\)，即，线段 \(xy\) 不与任何多边形的内部相交。 注意，\(xy\) 可能会与多边形的边界相交，例如，多边形的边就在可见图中。这与第 1 章(1.1.2 节)中使用的可见性概念相同， 只是现在考察的范围在多边形外部。图 8.1 中多边形的可见图如图 8.2 所示。

引理 8.2.1 可以通过三个步骤来证明:

1. 路径是多边形的。我们考虑相反的情况，路径包含一段曲线 \(C\)。\(C\)不可能完全位于多边形边界上，因为这些边界不是弯曲的。 那么 \(C\) 中必然有一段是凸的，它不接触任何多边形，并且可以被一条直线段捷径取代，这与路径是最短的假设相矛盾。
2. 路径的转折点位于多边形顶点处。"自由空间"中的任何转折都可以通过捷径(直线段)取代。
3. 路径的线段是可见边。这一点直接源于可见性及自由路径的定义。

由于可见图是有限的，该引理表明从 \(s\) 到 \(t\) 待搜索的候选路径数量是有限的。但是，图中的路径数量可能是虽 \(n\) 呈指数级增长。 因此，我们需要进一步的分析，才能得到一个实用的算法。首先我们简要探讨一下可见图的构建。

8.2.2. 构建可见图(Constructing the Visibility Graph)

为一组多边形构建可见图是一个极具吸引力且应用广泛的问题，并且已经得到了深入的研究。然而，详细解释这一过程会偏离运动规划的主题，因此这里仅作简要说明。

寻找可见图的边与寻找多边形的对角线几乎完全相同。两者仅有的细微差别在于，这里我们要处理的是多个多边形而不是仅仅一个，并且考虑的是外部可见性而非内部可见性。 很容易就可以得到一个 \(O(n^3)\) 的算法，对于每对顶点 \(x, y\)，检查线段 \(xy\) 是否与多边形的每一条边相交。由于图中的边数可能达到平方级，因此 \(\Omega(n^2)\) 是任何算法的下界。 我们在第 6.1 节中提到，利用排列(arrangements)可以得出一个最优的 \(O(n^2)\) 算法(O'Rourke 1987，第 8 章)。 经过长期的探索，Ghosh & Mount (1991) 找到了一种输出规模敏感的算法，对于具有 \(E\) 条边的图，复杂度为 \(O(n \log n + E)\)。 当然 \(E = O(n^2)\)，但如图 8.2 所示，通常 \(E\) 远小于 \(\binom{n}{2}\)。

8.2.3. Dijkstra 算法 (Dijkstra's Algorithm)

假设我们已经构建了可见图，并将其存储在某种方便的数据结构中。接下来的问题，也是本文的重点，就是如何在这个图中找到一条最短路径。 这是图论中的一个经典问题: 在加权图中寻找最短路径。这里，图的边上的权重就是这些边的长度，即端点之间的欧氏距离。

Dijkstra(1959) 提出了解决这个问题的一个精妙算法。在转向实现细节之前，我将先通过一个小例子来解释其核心思想。

颜料扩散 (Spreading Paint)

请看图 8.3 所示的可见图的一部分。为了减少杂乱，并未标出所有的可见边。试想一下，如果我们在源节点 \(s\) 处倾倒颜料，并将可见边想象是直径相同的细管， 那么油漆就会以恒定的速度，沿着所有可见边均匀扩散，即每单位时间扩散一个单位长度。可见图中第一个被颜料触及的顶点是 \(a\)，如图 8.3(a) 所示，它到 \(s\) 的距离是 1.93。 这是所有与 \(s\) 相关联的可见边中最短的一条。再过 0.12 个时间单位后，颜料触及顶点 \(b\)，如图 8.3(b)所示，并且颜料沿着所有其他路径又扩散了一小段距离。 在时刻 3.33，触及顶点 \(c\)，时刻 4.61，到达顶点 \(d\)。依此类推。

Dijkstra 算法的核心思想就是模拟这个颜料扩散的过程。当颜料到达目标 \(t\) 时，仿真所用的时间就是最短路径的长度。 我们在每个节点记录下，颜料最初是从哪个方向到达该节点的，就可以反向追溯，找到通往任意节点的完整最短路径。 这大致相当于给每个颜料分子标记上它所经过的路径，这样当第一个分子到达 \(t\) 时，我们就能获知其行进路径。

算法 (Algorithm)

对于可见图 \(G\)。Dijkstra 算法无需模拟颜料沿着每条可见边蔓延的连续过程，它只利用了离散步骤。该算法维护一棵以 \(s\) 为根节点的树 \(T \subset G\)， 涵盖了所有已被涂料触及的节点，即离散的颜料前沿(discrete paint frontier)。在每一步中，算法会检查与 \(T\) 中各节点关联的边，并添加一条边到 \(T\) 中。 该边需满足: (a) 到达 \(T\) 外部的一个节点 \(x \in G \setminus T\)；(b) 从 \(s\) 到 \(x\) 的距离在满足条件 (a) 的节点中是最短的。 条件 (b) 的目的是确保 \(x\) 是下一个被颜料触及的节点。

以图 8.3(b) 之后的算法步骤为例。此时节点 \(s, a, b\) 都已被颜料触及，所以 \(T = \{sa, sb\}\)。现在检查与这三个节点关联的所有边，并将它们的长度累加到这些节点的最短距离上。 例如，边 \(ad\) 的长度为 3.06，得出从 \(s\) 到达该点的距离为 \(1.93 + 3.06 = 4.99\)。边 \(sc\) 的长度为 3.33，得出从 \(s\) 出发的距离为 \(0 + 3.33 = 3.33\)。 可以看出，\(sc\) 适合添加到 \(T\) 中。

我们可以简洁地将 Dijkstra 算法表述为 Algorithm8.1。

时间复杂度 (Time Complexity)

分析 Dijkstra 算法的时间复杂度是算法分析中一个有趣课题，但这并非我们在此的重点。因此，我们只概述其中的一些问题，并将完整的分析留作练习。

while 循环执行的次数不可能超过 \(n\) 次，因为每次向 \(T\) 添加一条边都会到达一个新的节点，而总共有 \(n\) 个节点。 但是，在循环的每一步中需要检查的候选边数量可能是 \(O(n^2)\)，因为可见图中的边数可能是平方级的。 这给出了一个粗略的上界 \(O(n^3)\)。不过，显然，在每次迭代中都重新检查这些边是一种浪费。 事实上，该算法可以实现为在 \(O(n^2)\) 时间内运行，见练习 8.2.4[2]。结合可见图的 \(O(n^2)\) 构建过程，有以下定理。

8.2.4. 练习

1. 加强可见图引理? Strengthen visibility graph lemma? 引理 8.2.1 是否可以加强为: 最短路径绝不包含多边形的凹顶点(reflex vertex)?
2. Dijkstra 算法的复杂度 Complexity of Di algorithm。证明 Dijkstra 算法可以实现为 \(O(n^2)\) 时间复杂度的。
3. 圆盘障碍物 Disk obstacles。设计并分析一个算法，用于寻找点在 \(n\) 个不相交的圆盘障碍物之间的最短路径。
4. [Programming] 可见图 Visibility graph。编写程序构建一组多边形的可见图。只需实现 \(O(n^3)\) 的暴力算法即可。要尽量利用第 1 章中的三角分割代码。
5. 最短路径的数量 Number of shortest paths。对于总共有 \(n\) 个顶点的多边形障碍物，不包括起点 \(s\) 和终点 \(t\)，长度相等的最短路径最多有多少条?
6. 单位圆盘 Unit disks
   1. 假设所有障碍物都是单位圆盘，且像往常一样互不相交。\(s\) 和 \(t\) 之间的最短路径是否必须关于线段 \(st\) 单调?
   2. [open] 设计一个亚二次方(subquadratic)时间复杂度的算法，用于在存在单位圆盘的情况下寻找最短路径。
7. 多边形内的最短路径 Shortest path in a polygon(Guibas, Hershberger, Leven, Sharir & Tarjan 1987)。 设计一个算法来寻找多边形内部两点之间的最短路径。尝试实现优于 \(O(n^2)\) 的复杂度。