松弛

松弛是最短路径算法里的核心操作，对于边 (u, v)，权值为 w，若 dist[v]>dist[u]+w，就更新 dist[v]=dist[u]+w，尝试找到顶点 v 的更短路径；Dijkstra、Bellman‑Ford、SPFA、Floyd‑Warshall 都基于松弛思想。

January 1, 1990算法设计1分钟阅读

Dijkstra 算法的松弛操作：以结点 c 为当前结点，计算到邻接点 d、e 的候选距离；若候选距离小于结点原有距离，则更新最短距离`distance`与前驱结点`path_nodes`，完成松弛。

在图论与最优化算法中，松弛（Relaxation） 是指通过尝试一条新路径或更新约束条件，逐步逼近最优解的核心操作。根据使用场景的不同，“松弛”主要体现在以下两个重要领域：

在求图的最短路径算法（如 Dijkstra、Bellman-Ford、SPFA）中，松弛是最基础的操作。

假设用 $d[v]$ 表示从起点 $S$ 到节点 $v$ 的当前已知最短距离， $w(u, v)$ 表示从节点 $u$ 到节点 $v$ 的边权重。

如果发现通过节点 $u$ 到达节点 $v$ 的路径比之前已知的方法更短：

$d[u] + w(u, v) < d[v]$

那么我们就松弛边 $(u, v)$ ，更新 $d[v]$ 的值：

$d[v] = d[u] + w(u, v)$

直观理解：初始时，我们将起点到其他所有节点的距离估计值设为无限大（绷得紧紧的高估值），每次找到一条更优路径就将其放宽/收紧到更准确的值，就像把紧绷的橡皮筋逐步放松到自然舒适的位置。

void relax(int u, int v, int weight) {
    if (dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        parent[v] = u; // 记录路径
    }
}

Dijkstra 算法：贪心策略。每次选择未访问节点中 $d$ 值最小的节点，对其所有邻接边进行松弛操作（要求边权为非负）。
Bellman-Ford 算法：对图中的所有 $E$ 条边逐一轮询并尝试松弛，重复 $V-1$ 次，可处理负权边并检测负权环。
SPFA 算法：队列优化的 Bellman-Ford，仅对上一轮 $d$ 值被成功松弛的节点其后续边进行松弛。

在运筹学与 NP-hard 问题的近似算法中，松弛指的是放宽问题的约束条件，将复杂问题转化为易求解的子问题。

许多实际应用问题（如背包问题、TSP旅行商问题）属于整数线性规划（ILP），要求变量必须是整数，这是一个 NP-hard 问题。

松弛方法：去掉“变量必须为整数”这一约束，允许变量取任意连续实数（称为 线性规划松弛 / LP Relaxation）。

连续的线性规划问题可以在多项式时间内（如单纯形法、内点法）高效求解。
松弛后得到的解是原问题的边界/极限（求解最大化问题时，松弛解 $\ge$ 整数最优解；求解最小化问题时，松弛解 $\le$ 整数最优解）。

分支定界法（Branch and Bound）：利用松弛问题的解作为上界/下界，从而剪掉不可能产生最优解的分支。
近似算法（Approximation Algorithms）：求出松弛解后，通过“舍入（Rounding）”等技术将实数解转化为整数解，并证明其与理论最优解的偏差上限。

应用领域	松弛的本质含义	目的
最短路径算法	更新估计值：判断 $d[u] + w < d[v]$ 是否成立	逐步修正估计值，使其收敛到真实的最短距离
线性规划 / 优化	放宽约束条件（如取消整数限制）	将难解的 NP-hard 问题转化为易求解的连续数学问题