Bellman-Ford算法能否用于在只有正边的图上找到最短路径？
我知道Dijkstra算法只能用于边的正长度，而Bellman Ford算法也可以用于图的负长度。
假设我们有一个只有正边的图。贝尔曼·福特会给出和迪克斯特拉一样的结果吗？
共有2个答案
我想对Ami Tavory的回答补充一点。Bellman ford的算法可以稍微快一点，如果您可以检测到在任何过程中，没有节点值更新，然后从那里返回。如果没有节点更新，则证明每个节点遍历都已完成。
是的，它会给出同样的结果。不过，它会运行得更慢，因为它也可以用于具有负边的图（取决于是否没有负循环）。如果你看看高炉正确性的证明，那里没有假设一些边是负的。
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
我刚刚开始学习新的算法，但当我读到贝尔曼·福特关于极客的算法时，我陷入了困境：http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ 那里写着- 该算法以自下而上的方式计算最短路径。它首先计算路径中最多有一条边的最短路径的最短距离。然后，它计算最多有2条边的最短路径，依此类推。 在外环第i次迭代
-
有了贝尔曼-福特的算法，稍有改变：在第7行，我们把
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。
-
我知道Bellman-Ford算法适用于有向图。它对无向图有效吗？看起来，对于无向图，它将无法检测循环，因为平行边将被视为循环。这到底是真是假？算法可以应用吗？
-
Dijkstra不能用于最长路径，因为它使用的属性是当前最短路径肯定比其他路径短。这是正确的，当然，假设没有负边缘权重。这个概念也是为什么最长路径在Dijkstra上不起作用的原因，因为当前最长的路径不能保证以后不会有另一个更长的路径取更大的值。 另一方面，贝尔曼福特提供了在较差的性能负权重的灵活性。这意味着，对于贝尔曼福特来说，它不像迪克斯特拉那样在同样贪婪的财产上工作。所以这就是为什么我很困惑