algorithm - 计算图的最短路径时， "relax"操作的名字应该怎么理解？

Question

我的问题和标题一样。在计算图的最短路径时，经常会用到一个叫做relax的操作。很容易理解为什么使用这个操作，但这个名字的含义对我来说是个谜。“放松”是什么意思？

这里是用伪代码编写的Dijkstra示例:

DIJKSTRA(G,w,s)
　　1　INITIALIZE-SINGLE-SOURCE(G，s)
　　2　S ← Φ
　　3　Q ← V[G]
　　4　while Q≠Φ
　　5　    do u EXTRACT-MIN(Q)
　　6　    S ← S∪{u}
　　7　    for each vertex v∈Adj[u]
　　8　        do RELAX(u，v，w)

放松就在这里:

RELAX(u,v,w)  
    1  if d[v] > d[u] + w 
          d[v] ← d[u] + w

Answer 1

考虑 Dijkstra 算法的一种方式是，它正在求解对应于最短路径问题的线性规划。

maximize sum for v in V of d[v]
subject to
d[s] = 0
for each arc u->v, d[v] ≤ d[u] + w[u->v]  (*)

给定 LP 变量的赋值，我们可以定义每个约束的松弛。 slack 的含义是，当它为零时，约束的左边等于右边，当它为负时，约束被违反。此处，(*) 的松弛度为 d[u] + w[u->v] - d[v]。

一旦我们定义了 slack，RELAX 就是缓解 (*) 上的压力(即，消极的 slack)的程序。