Bellman Ford算法可以具有边缘的任意顺序吗？

我刚刚开始学习新算法，但是当我在极客上阅读极客的Bellman Ford算法时，就陷入了困境：-http: //www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

那里写着-

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

在外循环的第i次迭代之后，将计算最多i个边的最短路径。可以有最大| V |。–在任何简单路径中都有1条边，这就是为什么外循环运行| v |的原因 – 1次。这个想法是，假设不存在负权重循环，如果我们计算出最多具有i个边缘的最短路径，那么对所有边缘进行的迭代将确保给出最多具有（i + 1）个边缘的最短路径。

让我们通过下面的示例图了解算法。图像是从此来源获取的。

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

在下面的示例中，如果边的顺序为-（AB），（BE），（ED），（DC），（AC），（BC），（DB），（BD），则仅一次迭代将计算最短甚至具有2-3条边的路径，这与“首先为路径中最多具有一条边缘的最短路径计算最短距离。然后，它计算出具有最多2条边缘的最短路径，以此类推”相反在外循环的第ith次迭代之后，计算出最多具有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次。在第二次迭代后将距离最小化，因此第三次和第四次迭代不会更新距离。

是的，无论边沿处理的顺序如何，贝尔曼福特公司都可以工作。实际上，这就是您必须进行n-1迭代的原因。如果您知道，边缘的最佳顺序是什么-仅一次迭代就足够了。

考虑下图（所有边缘都有权重1）：

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

如果你处理的边缘顺序1->2，2->3，3->4。您将在一个迭代中找到从1到的最短方法4。对于边缘顺序排序3->4，2->3，1->2你会做所有3的迭代。

但是，n-1迭代是最坏的情况，无论边缘以什么顺序处理（如果没有负循环）。