algorithm - Dijkstra 算法中边缘的松弛

Question

在图论的上下文中，边的松弛 是什么意思？我在研究 Dijkstra 的单源最短路径算法时遇到了这个问题。

Answer 1

Here's对算法的一个很好的描述，也解释了松弛的概念。

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.