问题标签 [bellman-ford]

我需要创建一个测试，如果作为参数的图（有向图）具有负权循环，则返回 true，否则返回 false。

现在我创建了这个。理论上应该检查是否存在“通用”循环，而不是是否存在负循环。如何更改方法？有更简单或高效的吗？

谢谢

编辑：正如您从上面写的方法名称中看到的那样，我正在尝试实现 Bellman-Ford 的算法，并且我正在遵循这个伪代码：

我有一个用于贝尔曼福特算法的 C++ 源代码。它获取一个包含节点、边、源节点和目标节点的输入文件，并返回从一个节点到另一个节点的最短路径。文件类型为：

所以，我想让它从如下文件中读取输入：

这是我的源代码：

提前致谢

我知道 Dijkstra 的算法只能用于正边长度，而当图形也有负边时，可以使用 Bellman-Ford。

不过，假设我们有一个只有正边的图。Bellman-Ford 会给出与 Dijkstra 相同的结果吗？

I am working on a project with directed graphs where the weight of the edges all depend on a variable x. I'm trying to find the minimum value of x such that my graph does not contain any circuit of positive weight.

My question is -and it is probably pretty stupid but I don't see how- : How can I use a modified Bellman-Ford to check for the presence of positive circuits instead of negative circuits ?

Thanks.

Dijkstra 算法和 Bellman Ford 算法的时间复杂度不应该分别是O(|V|^2)和吗？O(|V|^3)我一直在从这里和这里阅读他们的伪代码。

Bellman Ford 算法和 Dijkstra 算法看起来非常相似，除了 Bellman Ford 算法在|V|时间上与 Dijkstra 算法执行相同的过程（其中|V|是节点数）。那么为什么我访问的关于这个主题的每一篇文章都说 Dijkstra算法运行在时间复杂度上，O(|v|^2)而 Bellman Ford 算法运行在O(|V||E|)时间复杂度上？我哪里做错了（如果我真的做错了）？

更新：你不觉得： |E| = (|V|^2 - |V|)/ 2如果每个节点都连接到其他节点？所以让我们假设每个节点都与其他节点相连。现在我们得到，O(|V|^3)对于贝尔曼福特算法。我对吗？

所以我们有O(|V||E|)= O(|V|(|V|^2 - |V|)/2) = O(|V|^3)。是对的吗？如果没有，我哪里做错了？

我正在使用 Bellman-Ford 找到通过具有一些负权重的图形的最短路径。该图没有循环的可能性，也没有双向连接。我想在图中找到 K 条最短路径，其中这些路径没有共同的节点。有没有我可以查找的算法来学习如何做到这一点？目前，简单的实现比速度更重要。

补充：感谢评论。需要明确的是，我正在寻找从指定开始节点到指定结束节点的前 K 种方法，没有其他节点相同。我需要一个全局最优值；依次找到最佳节点并删除节点并不能得到令人满意的结果。这个：https ://en.wikipedia.org/wiki/Yen%27s_algorithm给出了我正在谈论的内容，但在这种情况下，它需要非负边缘成本，并且它还允许共享节点。

已经提供了有向图的输入，并且我使用异步和同步 Bellman-Ford 算法找到了到特定节点“T”的最短路径。我试图找出删除某些边后对最短路径的影响。在我的方法中，我尝试将已删除边的起始节点处的距离标记为无穷大，并尝试应用异步 Bellman-Ford，但我被困在这一点上，因为其他节点不会更新它们的值，因为它们已经具有最短路径最小值。

谁能帮我找出一种方法来找到新的最短路径，而不必在新图上再次运行完整的算法？

我正在尝试改进 Bellman-Ford 算法的性能，我想知道改进是否正确。

我运行放松部分不是 V-1 而是 V 次，我得到了一个布尔变量，true如果在外循环的迭代期间发生任何放松，则设置该变量。如果在 n 处没有放松。n <= V 的迭代，它从最短路径的循环返回，但如果它在 n = V 迭代时松弛，这意味着我们有一个负循环。

我认为它可能会改善运行时间，因为有时我们不必迭代 V-1 次来找到最短路径，并且我们可以更早地返回，而且它也比使用另一个代码块检查循环更优雅。

证明当应用于线性规划问题的约束图时，Bellman-Ford 具有 Xj - Xi <= Wij 形式的约束，使函数 X1 + ... + Xn 在约束 Xj - Xi <= Wij 和 Xi <= 0。
我完全被困在这里。请提供一些提示来指导我完成解决方案。

我有以下代码：

我有一个问题path = nx.bellman_ford(digraph, start, return_negative_cycle=True)

这是错误：

回溯（最后一次调用）：文件“arb.py”，第 53 行，在 main() 文件“arb.py”，第 49 行，在主路径 = find_path(dg) 文件“arb.py”，第 24 行，在 find_path

路径 = nx.bellman_ford（有向图，开始，return_negative_cycle=True）

据我了解，这是正确的语法，所以我不太确定出了什么问题。

任何帮助，将不胜感激。