我们能将Bellman-Ford算法应用于无向图吗？
我知道Bellman-Ford算法适用于有向图。它对无向图有效吗？看起来，对于无向图，它将无法检测循环，因为平行边将被视为循环。这到底是真是假？算法可以应用吗？
共有2个答案
Bellman-Ford不适用于在包含负循环的图上找到最短路径，但是它可以在图上找到最短路径，并且可以检测图是否包含负循环，尽管它不会找到最短路径，因为不存在这样的路径。
事实上，任何无向图也是有向图。
只需指定任意边{u，v}两次（u，v）和（v，u）。
但不要忘记，这也意味着任何具有负权重的边都将被视为循环。由于Bellman-Ford算法只适用于不包含任何具有负权重的圈的图，这实际上意味着您的无向图不得包含任何具有负权重的边。
如果不是这样的话，使用贝尔曼福特是很好的。
-
我了解到Bellman-Ford算法的运行时间为O（| E |*| V |），其中E是边的数量，V是顶点的数量。假设图没有任何负加权圈。 我的第一个问题是，我们如何证明在（| V |-1）迭代中（每次迭代检查E中的每条边），它更新到每个可能节点的最短路径，给定一个特定的起始节点？有没有可能我们已经迭代了（|V |-1）次，但仍然没有得到到每个节点的最短路径？ 假设算法正确，我们真的能做得更好吗？我
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。
-
假设有一个具有
-
我刚刚开始学习新的算法，但当我读到贝尔曼·福特关于极客的算法时，我陷入了困境：http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ 那里写着- 该算法以自下而上的方式计算最短路径。它首先计算路径中最多有一条边的最短路径的最短距离。然后，它计算最多有2条边的最短路径，依此类推。 在外环第i次迭代
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
我知道这有点难，但我正在学习普林斯顿大学的算法课程。我尝试使用Bellman-Ford算法来检测边加权有向图中的负圈。 完整的代码实现可从以下网址获得：BellmanFordSP。java和EdgeWeightedDirectedCycle。JAVA具体来说，我被困在这一点上： 这个条件表示什么：。为什么我们只在这个特定的条件下检查负循环？