图论中边的松弛是什么？为何最短路径树中边的松弛需为零？

一、边的松弛（Slack）的定义与通俗解释 #

边的松弛值本质是当前已知的节点最短路径距离和通过这条边构建的路径距离之间的差值。你已经知道计算公式slack(u, v) = d[u] - (d[v] + w(v, u))（其中d[x]是起点到x的当前最短距离，w(v,u)是边v→u的权重），从全局意义来看，它就是衡量当前路径是否还有优化空间的“标尺”：

• 如果松弛值为正，说明走起点→v→u这条路线比当前记录的到u的最短路径更近，我们可以更新d[u]的值，相当于把之前“紧绷”的最短路径距离“松”到更优的数值；
• 如果松弛值为0或负，说明当前记录的d[u]已经是更优的，这条边没法给我们带来更短的路径。

举个生活化的例子：假设你从家（起点）到公司，之前记录的最快路线是打车，要30分钟（d[u]=30）。后来发现可以先坐地铁到商圈v（家到v最快10分钟，d[v]=10），再骑共享单车到公司（v到公司的骑行时间15分钟，w(v,u)=15），这条路线总耗时25分钟。此时松弛值就是30 - (10+15)=5，这个正数就代表你原来的路线还有优化空间，更新后到公司的最快时间就变成25分钟，松弛值也随之变为0。

二、为什么最短路径树中的边松弛必须为零？ #

最短路径树是从起点出发，由所有节点的最短路径构成的树结构，树中的每条边都是对应节点最短路径的最后一段。

对于树中的任意一条边(v,u)，u的最短路径必然是起点→...→v→u，也就是说u的最短距离d[u]一定等于起点到v的最短距离d[v]加上边v→u的权重w(v,u)，代入松弛公式就能得到slack(u, v) = d[u] - (d[v] + w(v, u)) = 0。

如果这条边的松弛值不为零，就会出现矛盾：

• 若松弛值为正，说明存在比当前d[u]更短的路径，那这条边就不该属于最短路径树；
• 若松弛值为负，说明d[v]不是起点到v的最短距离（因为通过u反向走可能有更短的路到v），这和最短路径树的定义冲突——树里的路径必须是起点到各节点的最短路径。

所以最短路径树中的边，松弛值必然为零。

内容的提问来源于stack exchange，提问作者mantagretz