什么是“松弛操作” (Relaxation)？

在图论的最短路径算法中，松弛是指：尝试通过一个中转点，来缩短到达某个目标点的路径长度。

如果发现通过中转点走更近，我们就更新（减小）目标点的最短距离估计值。这个过程就叫“松弛”。

1. 为什么叫“松弛”？（直观理解）

这个术语来源于数学和物理学。我们可以用橡皮筋的例子来形象地理解。

想象一下：

一开始，我们不知道从起点 $S$ 到终点 $B$ 的最短路，我们假设它无限远（或者用一条很长的绕远路的绳子连着），这时候绳子绷得很紧（估计值很大，即 dist[B] = ∞）。

当我们发现了一条从 $S$ 经过中间点 $A$ 再到 $B$ 的更短路径时，原本那根绕远路的紧绷绳子就可以松下来了，换成了一条更短的路线。路径的估计值变小了，压力变小了，所以叫“松弛”。

假设我们有两个顶点 $u$ 和 $v$，以及一条从 $u$ 到 $v$ 的边，权重为 $w(u, v)$。

松弛操作的伪代码逻辑：

if (dist[u] + w(u, v) < dist[v]) {
    dist[v] = dist[u] + w(u, v);
    path[v] = u; // 记录 v 的前驱节点是 u（为了还原路径）
}
`

人话翻译：

“我看了一下，如果我先走到 $u$，再从 $u$ 走到 $v$，这段路程的总长（dist[u] + w），是不是比我之前记下来的到 $v$ 的距离（dist[v]）更短？”

让我们来看一个具体的三角形例子：

场景：

起点是 S。
我们想去 Target (T)。
目前已知：
- $S \to T$ 的直接距离是 100。所以 dist[T] = 100。
- $S \to Middle (M)$ 的距离是 10。所以 dist[M] = 10。
现在我们要检查边 $M \to T$，它的权重是 20。

松弛步骤：

虽然核心都是 if (dist[u] + w < dist[v])，但在不同算法中，松弛发生的时机和次数不同：

算法	松弛的策略
Dijkstra	贪心松弛。每次只选距离起点最近的那个点，用它去松弛它的邻居。每个点只会被作为“中转点”用来松弛别人一次。
Bellman-Ford	暴力松弛。对所有的边，进行 $V-1$ 轮松弛。不管三七二十一，反复尝试缩短路径，直到不能再短为止。
SPFA	队列松弛。如果一个点被松弛成功了（变短了），那它后续可能也能帮它的邻居变短，所以把它入队，稍后用它去松弛邻居。
Floyd	矩阵松弛。`dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`。这里是把 $k$ 作为中转点，尝试松弛 $i$ 到 $j$ 的距离。