Bellman-Ford算法和步数
假设有一个具有100个顶点的有向图，例如V_1---
边的所有权重均为1。我们希望使用Bellman-Ford算法找到顶点1（V_1）到其他顶点之间的最短路径。该算法在每一步都以任意顺序检查所有边。如果在一个步骤中V_1到所有其他顶点之间的最短路径未更改（从以前的值），则算法将停止此算法中的步骤数取决于检查边缘的顺序。
这个算法的最大和最小步数是多少？
a) 100, 10000
b) 2, 100
c) 100, 100
d) 2, 99
任何人都可以告诉我为什么选择选项（2）来回答这个问题？
共有1个答案
Bellman-Ford算法在维基百科上给出。
如果选择了V_1和V_2，则需要两个步骤。如果V_1到V_1不是一个允许的输入，那么它不会变得更好，这可以通过一个步骤完成。
最坏的情况是，如果V_1和V_100作为输入：这需要100步才能到达V_100。
问题是：给定可能的输入，在示例图中，边到边之间的距离的最佳情况是什么，最坏情况是什么？
示例：输入为Bellman-Ford（顶点，边缘，Soucre）
会发生什么？
在这个特定的例子中，顶点V_1V_100，边缘E_1（从V_1到V_2等），源V_1。
步骤1：从头开始，即我们知道从V_1到V_1的最短路径
步骤2：沿着其中一条边。只有一条边，我们称之为E_1。此边从V_1到V_2。算法将遵循这条边。现在我们知道从V_1到V_2的最短路径沿着这条边走一步。V_1和V_2的步骤数为2。这是最短的非平凡路径。
现在确定V_1和V_100之间的距离的结果。在V_1和V_100之间有99条边，因为E_99从V_99到V_100。这需要多少步骤？此特定图形是否有更长的路径？
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
有了贝尔曼-福特的算法，稍有改变：在第7行，我们把
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。
-
我如何在Bellman-Ford算法中证明这一点： 如果没有负权重循环，则从源到接收器的每个最短路径最多有边，其中是图中的顶点数。 有什么想法吗？
-
我知道这有点难，但我正在学习普林斯顿大学的算法课程。我尝试使用Bellman-Ford算法来检测边加权有向图中的负圈。 完整的代码实现可从以下网址获得：BellmanFordSP。java和EdgeWeightedDirectedCycle。JAVA具体来说，我被困在这一点上： 这个条件表示什么：。为什么我们只在这个特定的条件下检查负循环？
-
我试图解决算法简介中的问题24-1，它指的是Yen对Bellman Ford algirithm的优化，我在wiki中找到了介绍，改进： Yen的第二个改进首先在所有顶点上分配一些任意的线性顺序，然后将所有边的集合划分为两个子集。第一个子集Ef包含所有边（vi， vj），使得i 不幸的是，我不能证明至少两个边松弛距离的方法如何匹配正确的最短路径距离：一个来自Ef，一个来自Eb。