如果我们可以在运行Bellman-Ford算法后再次松弛边缘，为什么会存在负循环
我们知道Bellman Ford是一个寻找负循环的算法。这里是Bellman-Ford输入的算法：给定一个图G（V，E），w（E）是权重输出：如果存在负循环，返回Yes。
1: set d(s) = 0 and d(v) = 1 for all v (- s
2: for i = 1 ... n-1 do
3: for every edge (u, v) in G do
4: if d(v) > d(u) + w(u,v) then
5: d(v) = d(u) + w(u,v)
6: end for
7: end for
8: for every edge (u, v) in G do
9: if d(v) > d(u) + w(u, v) then
10: return True
11:return False
第8行-第11行是检测负循环的另一个松弛，但是如果图中有负循环，为什么这些行保证检测负循环？
共有1个答案
您正在检测这样一个事实，即一些顶点对之间的最短路径太长，以至于它必须多次访问一些顶点，因此它包含一个循环。如果这个周期是长的
-
我知道这有点难，但我正在学习普林斯顿大学的算法课程。我尝试使用Bellman-Ford算法来检测边加权有向图中的负圈。 完整的代码实现可从以下网址获得：BellmanFordSP。java和EdgeWeightedDirectedCycle。JAVA具体来说，我被困在这一点上： 这个条件表示什么：。为什么我们只在这个特定的条件下检查负循环？
-
假设有一个具有
-
我刚刚开始学习新的算法，但当我读到贝尔曼·福特关于极客的算法时，我陷入了困境：http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ 那里写着- 该算法以自下而上的方式计算最短路径。它首先计算路径中最多有一条边的最短路径的最短距离。然后，它计算最多有2条边的最短路径，依此类推。 在外环第i次迭代
-
我知道Bellman-Ford算法适用于有向图。它对无向图有效吗？看起来，对于无向图，它将无法检测循环，因为平行边将被视为循环。这到底是真是假？算法可以应用吗？
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
最近，我看到了贝尔曼·福特的问题和一些事实如下： 我们知道bellman-ford算法在每个步骤中检查所有边，对于每个边，如果，d（v） 对于在具有顶点的图G中查找顶点的所有最短路径，此算法在