放松函数最短路径算法
在具有n顶点和m边的加权有向图G （具有正权重）中，我们要计算从顶点1到其他顶点的最短路径。 我们使用一维数组D[1..n] ， D[1]=0 ，其他数据用+infinity填充。 为了更新数组我们只允许使用Realx(u, v)
if D[v] > D[u] + W(u, v) then D(v):=D(u)+W(u,v)
其中W(u, v)是u-->v边的权重。 多少次我们必须调用Relax函数来确保对于每个顶点u ， D[u]等于从顶点1到u的最短路径的长度。
Solution: i think this is Bellman-Ford and m*n times we must call.
在Dijkstra和Bellman-Ford等人中，我们有Relax功能。 我们如何检测其中哪些？
引自CLRS书籍：
本章中的算法在放宽每个边缘的次数以及它们放松边缘的顺序方面有所不同。 Dijkstra算法和有向无环图的最短路径算法放松每个边缘一次。 Bellman-Ford算法放宽每个边| V | -1次。
对于Bellman-Ford和Dijkstra算法，我们将使用相同的松弛函数，但主要的不同在于，每个算法中松弛函数被调用的次数。
对于Bellman-Ford：
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
relax(u,v)
所以，放松函数将被称为每个边正好n - 1次。
对于迪克斯特拉：
while Q is not empty:
u ← vertex in Q with min dist[u] // Source node in first case
remove u from Q
for each edge(u,v) of u: // where v is still in Q.
relax(u,v)
end for
end while
在这种情况下，松弛函数在处理起始顶点时将被调用一次。
小结： Bellman-Ford算法，放松函数调用次数为m*n ，Dijkstra算法，调用次数为m ，其中m为边数， n为顶点数。
注意 ：代码是从维基百科进行采集和修改，为您带来更清晰的使用放松功能的视图
我们应该遍历每个边n - 1次：
for step <- 0 ... n - 1:
for edge <- edges
relax(edge)
有必要：设想一个有n个顶点的链。 我们需要完成n - 1步骤才能达到最后。
这足够了：在最佳路径中没有循环，最长的简单路径至多包含n - 1边。
所以答案是(n - 1) * m只是简单地遍历距离数组并进行更改（是的，它是Ford-Bellman的算法）。
但是，如果使用另一种算法（例如Dijkstra's），则对松弛函数的调用次数会减少（即， m ）。
所以这取决于我们正在使用的算法的细节。
链接地址: http://www.djcxy.com/p/35301.html