我们将介绍一些解决单源最短路径问题的算法。给定一个带权有向图 $G$ 和一个顶点 $s$，目标是找到从 $s$ 到所有其他顶点的最短路径。由于 $s$ 是这些路径的起点，因此被称为源顶点。

注意：各种最短路径算法通常使用带权有向图来建模底层网络。

由于在带权有向图中，一条最短路径的长度是路径上各边权重之和，而不是边的数量，因此广度优先搜索（BFS）不再适用于寻找最短路径。

一些著名的和不太知名的单源最短路径算法利用了“边松弛”思想，并采用由 Lester R. Ford Jr. 提出的一种特定的顶点属性初始化方案。我们在此介绍这一重要机制。

约定

源顶点通常记作 $\mathbb{s}$，除非另有说明。

回顾：从 $s$ 到 $v$ 的路径称为 $\mathbb{s} - \mathbb{v}$ 路径。

属性与初始化方案

对于带权有向图 $G$ 中的每个顶点 $v$，我们需要维护以下属性：

• $v.dist$ 存储目前为止已发现的所有 $s - v$ 路径中最短路径的长度。其初始化方式如下： s.dist &= 0\\ v.dist &= \infty \quad \text{对所有 } v \neq s \end{align*}$$ 符号 $\infty$ 表示一个非常大的数。

• $v.parent$ 存储当前已发现的最短 $s - v$ 路径中 $v$ 的前驱顶点。它对所有顶点初始化为 nil。

一旦找到到达 $v$ 的最短路径，$v.dist$ 就精确存储该最短 $s - v$ 路径的长度，而 $v.parent$ 存储该最短路径树中 $v$ 的父节点。

请注意，一旦父指针正确计算完成，就可以使用我们在之前练习中开发的递归 ShowPath 算法打印从源点到另一顶点的最短路径。

边松弛

给定一条边 $(u,v)$，如果满足 $u.dist + weight[u][v] \lt v.dist$ 则说明存在一条比当前已知路径更短的到达 $v$ 的路径，即先走长度为 $u.dist$ 的路径到达 $u$，再通过边 $(u,v)$ 到达 $v$。在这种情况下，我们希望更新 $v.dist$，使其存储更短路径的长度。

因此，边松弛指的是：当上述不等式成立时，将 $v.dist$ 更新为不等式左边的较小值。下图展示了两种不同场景。

路径松弛

路径松弛的思想对于理解许多最短路径算法为何能正确工作至关重要。核心思想如下：

考虑以下事实：

• 由于 $s.dist$ 初始化为 0，源点 $s$ 到自身的最短距离从一开始就已确定。

• 记住，路径中的子路径也是最短路径。每当路径的第一条边 $(s,w_1)$ 被松弛时，若 $w_1.dist$ 的值较大，则它一定会被更新为这条最短 $s - w_1$ 路径的长度。 $w_1.dist = s.dist + weight[s][w_1]$ 无论未来松弛哪些边，这个值都无法再降低至更低。

• 类似地，当在未来某个时刻松弛边 $(w_1,w_2)$ 时，$w_2.dist$ 会被设为最短 $s - w_2$ 路径的长度。未来的边松弛操作不会再降低 $w_2.dist$ 的值，因为它已被设置为最小可能值。

• 同理，一旦 $w_i.dist$ 被设为最小可能值，将来在适当时间松弛边 $(w_i,w_{i+1})$ 将确保 $w_{i+1}.dist$ 也被设为最小可能值。

  $w_{i+1}.dist = w_i.dist + weight[w_i][w_{i+1}]$

考虑以下事实。

• 由于 $s.dist$ 初始化为 $0$，源点 $s$ 到自身的最短距离从一开始就已计算出来。

• 记住，路径中的子路径也是最短路径。每当路径的第一条边 $(s,w_1)$ 被松弛时，若 $w_1.dist$ 包含更大的数值，它将被保证更新为这条最短 $s - w_1$ 路径的长度。

  $$w_1.dist = s.dist +weight [s][w_1]$$

  无论未来松弛哪些边，该值都无法进一步降低至低于此最小值。

• 类似地，当在未来某个时刻松弛边 $(w_1,w_2)$ 时，$w_2.dist$ 会被设为最短 $s - w_2$ 路径的长度。未来的边松弛操作不会降低 $w_2.dist$ 的值，因为它已被设为最小可能值。

• 同样地，一旦 $w_i.dist$ 被设为最小可能值，将来在适当时间松弛边 $(w_i,w_{i+1})$ 将确保 $w_{i+1}.dist$ 也被设为最小可能值。

  $$w_{i+1}.dist = w_i.dist + weight[w_i][w_{i+1}]$$

在任意一组边松弛操作中，如果存在一个子序列，其中某条最短路径的边按其在路径中出现的顺序被松弛，则称该过程为对该路径的路径松弛。在所提出的初始化方案下，对一条最短路径进行路径松弛保证能够正确计算该路径上各顶点的最短路径长度。

注意：依赖路径松弛原理来保证正确性的最短路径算法，并不假设从源点到所有其他顶点的最短路径在事先已知，因为这会违背这类算法的设计初衷。相反，它们的设计目标是确保以某种方式松弛边，从而必然计算出所有可能存在最短路径的长度。

示例

在以下幻灯片中，左侧是一个有向图，右侧是一个随机的待松弛边序列。幻灯片展示了如何在路径 $P=\langle s, v_1,v_3, v_4\rangle$ 的边按正确顺序被松弛时，路径上各顶点到源点的距离被正确计算。特别地，路径 $P$ 的第一条边 $(s,v_1)$ 在第二条边 $(v_1, v_3)$ 之前被松弛，而后者又在第三条边 $(v_3, v_4)$ 之前被松弛。