问题标签 [bellman-ford]

我对这段代码有什么问题一无所知。它没有按预期工作。它预计会显示从顶点 1 到 N 的最短路径。但它在很多情况下都失败了。一个这样的情况是 3 1 1 2 1 它显示答案为 1 25 -1 3 这是错误的......任何帮助将不胜感激。谢谢。

我很难理解为什么 Bellman-Ford 是 O(VE) 而不是 Θ(VE)。它不是总是运行 |V|-1 的for循环并每次都放松所有边缘吗？

令 G = (V, E) 为边权重非负的连通有向图，令 s 和 t 为 G 的顶点，令 H 为 G 删除部分边得到的子图。假设我们想将 G 的一条边重新插入到 H 中，以便在结果图中从 s 到 t 的最短路径尽可能短。描述和分析一种算法，以选择要重新插入的最佳边。

我认为它需要与我们删除的每条边一起使用贝尔曼福特算法，然后从所有路径中找到最短路径..但​​是这个运行时间太大了..有人有其他想法吗？谢谢 ：）

我正在尝试为映射到具有非负权重边的有向图的问题找到启发式方法。然而，每条边都与两个权重属性相关联，而不仅仅是一个权重（例如，一个是距离，另一个是显示道路的 4G LTE 覆盖范围有多好！）。dijkstra、或任何其他算法是否有任何特定的变体来Bellman Ford实现这一目标？当然，一个简单的解决方法是手动将单个权重属性作为所有这些属性的组合，但这看起来并不好。

它可以推广到具有多个属性的情况吗？

我们有一个有 100 个顶点的有向图。v1 --> v2 --> ... v100 并且所有边的权重都等于 1。我们想使用 bellman-ford 来查找从 v1 到其他顶点的所有最短路径。该算法在每一步中以任意顺序检查所有边。如果在每一步中到所有其他顶点的最短距离 v1 没有改变，则该算法停止。步数与检查边的顺序有关。这个问题的最小和最大步数是多少？

解决方案：2 和 100。

这个解决方案将如何实现？

因此，如果我尝试使用 Bellman Ford 算法找到最短路径，使用此方法测试是否存在路径：

如果我有一个负循环，那么这个算法会发生什么？它是否仍然返回 true，因为我知道 Dijkstra 的算法不适用于负循环，但 Ford 的算法呢？

最近一直在研究贝尔曼福特算法。我怀疑如果有向图中的负权重循环可以从源顶点到达，那么所有节点或某些节点都不存在最短。这是我的贝尔曼福特实现。

我很难理解如何计算到无穷大的关键点。

假设我们有一个网络

A-B-C-D-E

每个链接的成本为 1。

根据塔南鲍姆的说法，

当A下降时，B将其成本更新A为无穷大。但是B收到一个广告C，上面写着“我可以A用 2 的成本到达”。现在，B可以C以 1 的成本到达，因此它将距离更新A为 3。

在下一部分我有一个问题。

他说，

现在C注意到它的两个邻居都可以A以 3 的成本到达。“所以C将距离更新A为 4”

为什么会这样？因为已经C认为它可以A通过 2 的成本达到。

根据贝尔曼福特方程，这个成本小于成本 3+1=4。为什么不应该简单地将距离保持为 2 而不是将其更改为 4？

如何在有向加权图中找到负循环。我知道 Bellman Ford 算法是如何工作的，并且它告诉我是否存在可达到的负循环。但它没有明确命名它。

如何获得循环的实际路径 v1,v2,...vk,v1？

应用标准算法后，我们已经进行了 n-1 次迭代，应该不可能有进一步的改进。如果我们仍然可以降低到节点的距离，则存在负循环。

假设边 (v,u) 是贝尔曼福特算法在第 n 次迭代中失败的边 - d(u) > d(v) + w(v,u)。所以我们知道 v,u 是负循环的一部分，但问题是我如何检测特定循环？

我正在使用 JGraphT 在 Java 中实现 Bellman Ford 最短路径算法。由于有一些边缘，应优先考虑，它们的边缘权重设置为-1。

例如：

A <-> B：10

A <-> C: 10

C <-> B：-1

B <-> D：10

所以在这种情况下，路径应该看起来像 A -> C -> B -> D。子路径 A->C->B 应该优先于 A->B。

现在问题来了：算法在 C 和 B 之间找到循环，因此 C->B 和 B->C 路径被多次添加（以减少总路径成本，因为 B<->C 的权重为负） .

现在的问题是：是否有可能避免这样的循环？我在 API 中没有找到任何选项。Graph 对象的 isAllowingLoops() 方法返回“false”。

你能给我一些提示吗？

提前致谢！