在Dijkstra算法中放松边缘

Question

relaxation of an edge在图论的背景下意味着什么？我在研究Dijkstra的单源最短路径算法时遇到了这个问题.

Answer 1

这里有一个很好的算法描述,也解释了放松的概念.

"松弛"的概念来自最短路径的估计与螺旋拉伸弹簧的长度之间的类比,螺旋拉伸弹簧不是为压缩而设计的.最初,最短路径的成本是高估的,就像一个伸展的弹簧.当找到较短的路径时,估计的成本降低,并且弹簧放松.最终,找到最短路径(如果存在的话)并且弹簧已经放松到其静止长度.

这种解释毫无意义。弹簧是边缘吗？那么当一个弹簧放松时，其他弹簧会发生什么情况呢？为什么一开始大家都不放松呢？或者弹簧是最短路径吗？那么它们不可压缩到什么程度呢？为什么要谈论“放松弹簧”而不是“缩短绳索”？我听说“放松”来自运筹学，但我还无法弄清楚细节...... (4认同)
是否有理由告诉我们 EDGE 是松弛的，而不是到节点的路径 v. 为什么是“EDGE”松弛而不是“PATH”松弛 (2认同)

Answer 2

Dijkstra算法中的松弛过程是指更新连接到顶点v的所有顶点的成本,如果通过包含v的路径来改善这些成本.

Answer 3

放宽边缘(您可以在其他最短路径算法中找到的概念)试图通过使用另一个顶点来降低到达顶点的成本.

您正在计算从起始顶点(例如S)到所有其他顶点的距离.在某些时候,您有中间结果 - 当前估计.对于某些顶点u和v,放松是你检查的过程:

if directly_connected(v, u)
    if est(S, v) > est(S, u) + dist(u,v)
       est(S, v) = est(S, u) + dist(u, v)

其中est(S,a)是距离的当前估计,并且dist(a,b)是图中邻居的两个顶点之间的距离.

您在松弛过程中基本上检查的是天气,您通过c "转移"路径可以改善从a到b的当前估计(这种"转移"将是从a到c以及从c到b的路径的长度).