在 Dijkstra 的最短路径算法和其他算法中，检查边以查看它是否提供到节点的更好路径被称为松弛边。为什么叫放松呢？
问问题
9518 次
2 回答
42
In general mathematically, relaxation is making a change that reduces constraints. When the Dijkstra algorithm examines an edge, it removes an edge from the pool, thereby reducing the number of constraints.
It's not horribly useful terminology, but think how cool you'll sound saying it.
于 2012-05-24T23:58:51.293 回答
2
我认为这个问题与当前接受的答案中讨论的数学概念无关。我的答案基于 Cormen (CLRS) 书的第二版，特别是第 24 章关于放松的部分。
上下文：您正在搜索节点s和所有其他节点之间的最短路径。假设您有两个节点u和v。您已经为他们准备了一条中间路径。
Relax(u,v)是一个函数，应该读作“使用u放松v ”。我更喜欢将函数理解为“使用u缩短v到s的距离”。您在问自己是否应该放弃当前的路径sv转而将其转换为suv。你所要做的就是看看su的距离加上箭头uv的额外成本是否比距离sv更好。图片举例说明功能
于 2018-06-06T03:27:40.270 回答