的边缘在Dijkstra算法松弛 [英] Relaxation of an edge in Dijkstra's algorithm

问题描述

这是什么 边的放松 的意思是图论的背景下？我碰到这个，而在Dijkstra算法单源最短路径学习了。

What does relaxation of an edge mean in the context of graph theory ? I came across this while studying up on Dijkstra's algorithm for single source shortest path.

推荐答案

这里的一个这也解释了缓和的概念的算法很好的说明。

Here's a nice description of the Algorithm that also explains the notion of relaxation.

的松绑的概念来自于估值之间的类比   最短路径和一个螺旋拉伸弹簧的长度，其中的   不用于COM pression。最初，最短成本   路径是高估了，比做伸出来的春天。由于短   路径被找到时，估计的成本降低，并且弹簧是   轻松。最终，最短路径，如果存在的话，没有发现   春天已经放宽到了休息的长度。

The notion of "relaxation" comes from an analogy between the estimate of the shortest path and the length of a helical tension spring, which is not designed for compression. Initially, the cost of the shortest path is an overestimate, likened to a stretched out spring. As shorter paths are found, the estimated cost is lowered, and the spring is relaxed. Eventually, the shortest path, if one exists, is found and the spring has been relaxed to its resting length.

这篇关于的边缘在Dijkstra算法松弛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！