编程里的“松弛”是什么意思?

发布网友发布时间：2022-04-27 11:36

我来回答

共2个回答

热心网友时间：2023-09-15 10:55

意思是对于每个顶点v∈V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计（shortest-pathestimate）。

π[v]代表S到v的当前最短路径中v点之前的一个点的编号,我们用下面的Θ(V)时间的过程来对最短路径估计和前趋进行初始化。

INITIALIZE-SINGLE-SOURCE(G,s)。

1、for each vertex v∈V[G]。

2、do d[v]←∞。

3、π[v]←NIL。

4、d[s]←0。

扩展资料：

经过初始化以后，对所有v∈V，π[v]=NIL，对v∈V-{s}，有d[s]=0以及d[v]=∞。

在松弛一条边(u,v)的过程中，要测试是否可以通过u，对迄今找到的v的最短路径进行改进；如果可以改进的话，则更新d[v]和π[v]。一次松弛操作可以减小最短路径估计的值d[v]，并更新v的前趋域π[v](S到v的当前最短路径中v点之前的一个点的编号)。下面的伪代码对边(u,v)进行了一步松弛操作。

参考资料来源：百度百科-松弛

热心网友时间：2023-09-15 10:55

松弛就是更新两点间的最短路径。
与Bellman算法类似，这个类似不恰当，SPFA本身就是队列优化的Bellman。SPFA在初始时是要将点点间距离设为MAX的，之后从起点开始，找到与它有通路的所有节点，这时更新最短路径的存储数组并将这些节点入队。这里的更新操作就是松弛，比如原先1节点到2节点的距离是MAX，现在因为有通路且1到2的距离是a，那么就更新（松弛）。我觉得应该是讲的挺明白了，没明白的话Hi我。