Bellman算法能有任意的边序吗？

Question

我刚刚开始学习新的算法，但是当我读到极客们关于极客的行李员福特算法时，我被困住了:- http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

上面写着-

该算法以自下而上的方式计算最短路径.它首先计算最短路径的最短距离，而最短路径中最多有一条边。然后，计算最短路径，最多有2条边，以此类推.

经过外循环的第1次迭代，求出了边数最多为i的最短路径。在任何简单的路径中都可以有最大的x-V-1边，这就是为什么外循环运行了很多次。其思想是，假设不存在负权环，如果我们计算了最多有i条边的最短路径，那么对所有边的迭代保证给出带最多(i+1)边的最短路径。

让我们用下面的例子图来理解算法。这些图像是从这个来源拍摄的。

设给定的源顶点为0。将所有距离初始化为无限，但源本身的距离除外。图中的顶点总数为5，因此必须对所有边进行4次处理。

在下面的例子中，如果边的顺序是- (AB)，(BE)，(ED)，(DC)，(AC)，(BC)，(DB)，(BD)，那么在一次迭代中，它将用2-3条边计算最短路径，这与“它首先计算路径中最多有一条边的最短路径的最短距离”的说法相矛盾。然后，计算最短路径，最多有2条边，以此类推.在外循环的第i次迭代之后，计算出最多有i个边的最短路径“，因此，如果改变边的顺序，这条语句将证明是假的。

让我们用下面的例子图来理解算法。这些图像是从这个来源拍摄的。

设给定的源顶点为0。将所有距离初始化为无限，但源本身的距离除外。图中的顶点总数为5，因此必须对所有边进行4次处理。

​

​

设所有边按下列顺序处理：(B，E)，(D，B)，(B，D)，(A，B)，(A，C)，(D，C)，(B，C)，(E，D)。当第一次处理所有边缘时，我们得到跟踪距离。第一行显示初始距离。当处理边(B，E)，(D，B)，(B，D)和(A，B)时，第二行显示距离。第三行显示(A，C)处理时的距离。第四行显示处理(D，C)、(B、C)和(E，D)的时间。

​

第一次迭代保证给出的最短路径最多为1边长。当第二次处理所有边(最后一行显示最终值)时，我们得到以下距离。

​

​

第二次迭代保证给出的最短路径最多有2条边长。该算法对所有边缘再进行2次处理。距离在第二次迭代之后被最小化，所以第三次和第四次迭代不会更新距离。

Answer 1

是的，行李员福特公司的工作，无论是按什么顺序处理边缘。事实上，这就是为什么您必须执行n-1迭代的原因。如果你知道，什么是边的最佳顺序-只有一个迭代就足够了。

考虑下面的图(所有边都有权重1)：

 (1) --> (2) --> (3) --> (4) 

如果您按照顺序1->2、2->3、3->4处理边缘。您将在一次迭代中找到从1到4的最短路径。对于按3->4、2->3、1->2顺序排序的边，您必须执行所有3迭代。

然而，n-1迭代是最坏的情况，无论按什么顺序处理边(如果没有负循环)。

Answer 2

是这样的。放松的顺序并不重要。

例如,

​

有3个节点，因此可以进行两次迭代松弛。如果松弛从节点b开始，再到节点a，则第一次迭代将产生b:无穷大，a:2，则第二次迭代为b:5，a: 2。在第一次迭代b中，由于只使用一条边，所以只能更新距离它一条边的节点。第二次迭代是从源到任何地方使用两个边，所以b最终可以被更新。在第一次迭代中，b根本无法被更新，因为a还没有准备好。

那我们来看一下前向更新如何？在第一次迭代中，它是a: 2和b: 5。第二次迭代又是a: 2和b: 5。向前看，所有连续的节点都可以使用更新的距离做好准备，所以更多的迭代不会改变值。但是，如果我对101个节点执行100次迭代，而我正在执行前向更新，那么会发生什么呢？是否有可能在第一次迭代中更新了所有内容，直到第99次迭代都没有变化，而在第100次迭代时突然有一个节点的距离缩小了？不，这是不可能的，因为前向更新不会在第一次迭代之后引起更改，除非存在负循环。

您可以在这里阅读更多关于Bellman的信息：https://medium.com/@logicdevildotcom/dynamic-programming-applied-to-graphs-f33b6b8a8247。

Answer 3

与注释一起引用的表行。

第四行显示处理(D，C)、(B、C)和(E，D)的时间。

是不对的这意味着存在一个长度为2的从A到C的路径，该路径最多由一个边组成，但是这样的路径并不存在。