Bellman-Ford和一些关于图G的事实？
我们知道bellman-ford算法检查每一步中的所有边，如果，
d（v）
然后更新d（v），使得w（u，v）是边（u，v）的权重，d（u）是顶点的最佳查找路径长度u。如果在一个步骤中我们没有顶点更新，那么算法将终止。在假设该算法的情况下，求出了图G中n顶点k后的所有最短路径
1） 来自s的所有最短路径中的边数最多为k-1
2） 来自s的所有最短路径的权重最多为k-1
3） 图中没有负循环。
我确信其中一个是正确的，但我的助教说其中两个是正确的。对这些问题有什么想法或提示吗？
共有1个答案
让我们一次看一个陈述：
1） 来自s的所有最短路径中的边数最多为k-1
考虑下面的图表：
s ---e1---> n1 ---e2---> n2 ---e3---> n3
如果边按给定顺序排列（e1、e2、e3），则在第一次迭代后，每个节点的距离都是正确的（检查e1更新n1，然后检查e2更新n2，依此类推）。因此，在这种情况下，算法在k=2次迭代后停止，因为第二次迭代不会改变任何东西。最长最短路径中的边数为3和3
2） 来自s的所有最短路径的权重最多为k-1
边的数量和它们的总权重都不受k-1的限制。考虑上述示例中的所有边都具有1000的权重。很明显，没有连接到k。
3） 图中没有负循环。
如果您像以前一样定义算法（在未进行任何更改时终止），则这是正确的。任何负循环都会导致无限循环，因为该循环中顶点的距离会连续减小。
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。
-
我对贝尔曼-福特做了一点修改，这样它只能“有用”放松。也就是说，d（v）的松弛被更新了。 现在，如果所有最短路径最多有k条弧。那么最坏情况下的运行时是O（V*k），因为在这个智能版本中我们只经过k个弧。这比原来的O（V*E）快一点，因为| k| 有谁能告诉我一种图的类型，这种改进的版本并不比原来的Bellman-Ford算法好？也就是说，最佳情况下的性能是O（V*E）
-
假设有一个具有
-
最近，我看到了贝尔曼·福特的问题和一些事实如下： 我们知道bellman-ford算法在每个步骤中检查所有边，对于每个边，如果，d（v） 对于在具有顶点的图G中查找顶点的所有最短路径，此算法在
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
我知道Bellman-Ford算法适用于有向图。它对无向图有效吗？看起来，对于无向图，它将无法检测循环，因为平行边将被视为循环。这到底是真是假？算法可以应用吗？