正电路的Bellman-Ford算法
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。
我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？
谢谢。
共有2个答案
如果你想找到最短路径，并且不想使用负边，你可以使用Dijkstra算法，它与Bellman-Ford算法非常相似。
但是，如果您只想访问可能权重较低的边，可以查看“Prim算法”或“Kruskall算法”，它们用于查找图的“最小生成树（MST）”。
Dijkstra算法
普里姆算法
克鲁斯卡尔算法
如何使用改进的Bellman-Ford来检查正电路而不是负电路的存在？
将所有权重更改为负值：
w'(u,v) = -w(u,v)
然后简单地运行常规BF。
您可以对该值x运行二进制搜索，以查找负循环所需的最小值，例如，在BF的O（logx）调用中。
找到进行负循环所需的边（u，v）的最小权重的更有效解决方案是移除该边，找到从v到u的最短路径。
现在，您可以知道边的权重应该是多少，以获得权重为0的循环（-d（v，u）），除此之外的任何内容-您有一个正循环，而不是负循环。
-
我试图解决算法简介中的问题24-1，它指的是Yen对Bellman Ford algirithm的优化，我在wiki中找到了介绍，改进： Yen的第二个改进首先在所有顶点上分配一些任意的线性顺序，然后将所有边的集合划分为两个子集。第一个子集Ef包含所有边（vi， vj），使得i 不幸的是，我不能证明至少两个边松弛距离的方法如何匹配正确的最短路径距离：一个来自Ef，一个来自Eb。
-
假设有一个具有
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。
-
我如何在Bellman-Ford算法中证明这一点： 如果没有负权重循环，则从源到接收器的每个最短路径最多有边，其中是图中的顶点数。 有什么想法吗？
-
有了贝尔曼-福特的算法，稍有改变：在第7行，我们把
-
我知道这有点难，但我正在学习普林斯顿大学的算法课程。我尝试使用Bellman-Ford算法来检测边加权有向图中的负圈。 完整的代码实现可从以下网址获得：BellmanFordSP。java和EdgeWeightedDirectedCycle。JAVA具体来说，我被困在这一点上： 这个条件表示什么：。为什么我们只在这个特定的条件下检查负循环？