Bellman-Ford算法的正确性，我们还能做得更好吗？
我了解到Bellman-Ford算法的运行时间为O（| E |*| V |），其中E是边的数量，V是顶点的数量。假设图没有任何负加权圈。
我的第一个问题是，我们如何证明在（| V |-1）迭代中（每次迭代检查E中的每条边），它更新到每个可能节点的最短路径，给定一个特定的起始节点？有没有可能我们已经迭代了（|V |-1）次，但仍然没有得到到每个节点的最短路径？
假设算法正确，我们真的能做得更好吗？我突然想到，在一个特定的图中，并不是所有的边都是负加权的。贝尔曼-福特算法似乎很昂贵，因为每次迭代都要经过每个边缘。
共有1个答案
从源到任何顶点的最长可能路径最多涉及图形中的所有其他顶点。换句话说，你不会有一条路径经过同一个垂直面不止一次，因为这必然会增加权重（这是真的，因为没有负循环）
在每次迭代中，您将在该路径的下一个顶点上更新最短路径权重，直到| V |-1次迭代后，您的更新必须到达该路径的终点。在此之后，将不会有任何顶点具有非紧值，因为您的更新已覆盖该长度内的所有最短路径。
这种复杂性很小（至少对于BF而言），请考虑一条连接顶点的长线。选择最左边的作为源-你的更新过程必须一次从那里到另一边。现在，您可能会争辩说，您不必以这种方式检查每条边，因此，让我们加入一些具有非常大权重（N）的随机边
-
我试图解决算法简介中的问题24-1，它指的是Yen对Bellman Ford algirithm的优化，我在wiki中找到了介绍，改进： Yen的第二个改进首先在所有顶点上分配一些任意的线性顺序，然后将所有边的集合划分为两个子集。第一个子集Ef包含所有边（vi， vj），使得i 不幸的是，我不能证明至少两个边松弛距离的方法如何匹配正确的最短路径距离：一个来自Ef，一个来自Eb。
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
我知道Bellman-Ford算法适用于有向图。它对无向图有效吗？看起来，对于无向图，它将无法检测循环，因为平行边将被视为循环。这到底是真是假？算法可以应用吗？
-
假设有一个具有
-
我刚刚开始学习新的算法，但当我读到贝尔曼·福特关于极客的算法时，我陷入了困境：http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ 那里写着- 该算法以自下而上的方式计算最短路径。它首先计算路径中最多有一条边的最短路径的最短距离。然后，它计算最多有2条边的最短路径，依此类推。 在外环第i次迭代
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。