从CLRS中理解BELLMAN算法

Question

考虑一下这个简单的图：

S -> A -> B -> C

在CLRS中，作者实现了一个循环，该循环适用于for \-1。但是根据path-relaxation property，简单路径P可以是< s，a，b，c >。

使用path-relaxation property，我们将按以下顺序放宽P的边缘

(S,A),(A,B),(B,C)

因此，对于我们的|V| - 1迭代，我们将在一次传递中完成。我可以理解|V| -1传递的使用，如果path-relaxation property没有指定我们放松路径，从‘源’开始。

这里有什么意义呢？我的解释哪里出了问题。

Answer 1

因为任意两个节点之间的任何最短路径都不能包含大于|V|节点或|V|-1边缘的路径。通过放松|V|-1时间的边，我们确定了两个节点之间的最佳距离(如果存在最优路径的话)。