计算图的最短路径时，"relax"操作的名称应该怎么理解？
How should I understand the name of the "relax" operation when computing the shortest path of a graph?
我的问题和标题一样。在计算图的最短路径时，经常会用到一个名为relax的操作。很容易理解为什么使用这个操作，但这个名字的含义对我来说是个谜。
“放松”是什么意思？
这是 pseudo-code 的 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
考虑 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。 slack 的含义是，当它为零时，约束的左边等于右边，当它为负时，约束被违反。在这里，(*) 的松弛度是 d[u] + w[u->v] - d[v].
一旦我们定义了松弛，RELAX 就是缓解 (*) 上的紧张（即负松弛）的过程。
我的问题和标题一样。在计算图的最短路径时，经常会用到一个名为relax的操作。很容易理解为什么使用这个操作，但这个名字的含义对我来说是个谜。 “放松”是什么意思？
这是 pseudo-code 的 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
考虑 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。 slack 的含义是，当它为零时，约束的左边等于右边，当它为负时，约束被违反。在这里，(*) 的松弛度是 d[u] + w[u->v] - d[v].
一旦我们定义了松弛，RELAX 就是缓解 (*) 上的紧张（即负松弛）的过程。