问题标签 [bellman-ford]

据我所知，当一个路由器提供另一个旧信息时，就会发生计数到无穷大，该旧信息继续通过网络传播到无穷大。从我读到的内容来看，这肯定会在删除链接时发生。

所以在这个例子中，Bellman-Ford 算法将为每个路由器收敛，它们彼此都有条目。R2 会知道它可以以 1 的成本到达 R3，R1 会知道它可以通过 R2 以 2 的成本到达 R3。

如果 R2 和 R3 之间的链路断开，则 R2 将知道它不能再通过该链路到达 R3，并将其从表中删除。在它可以发送任何更新之前，它可能会收到来自 R1 的更新，该更新将通告它可以以 2 的成本到达 R3。R2 可以以 1 的成本到达 R1，因此它将更新一条到R3 通过 R1 的成本为 3。R1 稍后将接收来自 R2 的更新，并将其成本更新为 4。然后它们将继续相互提供不良信息，直至无穷大。

我在几个地方看到的一件事是，除了链接脱机之外，可能还有其他原因导致无穷大，例如更改链接的成本。我开始考虑这个问题，据我所知，在我看来，增加链接的成本可能会导致问题。但是，我不认为降低成本可能会导致问题。

例如，在上面的示例中，当算法收敛时，R2 有一条到 R3 的路由，成本为 1，而 R1 有一条经过 R2 到 R3 的路由，成本为 2。如果 R2 和 R3 之间的成本增加到5. 那么这将导致同样的问题，R2 可以从 R1 获得更新，通告成本 2，并通过 R1 将其成本更改为 3，然后 R1 将其通过 R2 的路由更改为成本 4，依此类推。但是，如果融合路由的成本降低，则不会引起变化。它是否正确？可能导致问题的链接之间的成本增加，而不是成本降低？还有其他可能的原因吗？让路由器下线和链接出去是一样的吗？

我想在大量图上对贝尔曼福特算法进行执行时间分析，为了做到这一点，我需要生成大量随机 DAGS，并且可能具有负边权重。

我在python中使用networkx。networkx 库中有很多随机图生成器，但是哪个会返回带有边权重和源顶点的有向图。

我正在使用 networkx.generators.directed.gnc_graph() 但这并不能完全保证只返回一个源顶点。

有没有办法在有甚至没有networkx的情况下做到这一点？

我不知道在哪里发布这个问题，我只想知道我是否正确地进行了这个跟踪。我得到了这张图

这是问题：

在以下有向图上显示 Bellman-Ford 算法的轨迹，使用顶点 t 作为源。在每一遍中，按照(x, t),(y, z),(u, t),(y, x),(u, y),(t, x),(t, y) 的顺序松弛边缘），（t，z），（z，x），（z，u）。每次通过后显示 d 值。图表是否有负权重的圆圈？您如何使用 Bellman-Ford 算法对其进行检查？

我得到的答案是 u=12, t=0, x=4, y=12, and z=-3，而且它没有负权重圆。这个问题值得很多分，一个错误意味着减去很多，所以我不知道还有谁必须为我检查这个。谢谢你。

我一直在尝试编写 Bellman Ford 算法以在图中找到最短路径，虽然我有一个可行的解决方案，但它运行得不是很快，我相信如果我可以更快使用 numpy 而不是我目前的方法。

这是我使用 for 循环的解决方案：

输入文件如下所示 -> https://github.com/mneedham/algorithms2/blob/master/shortestpath/g_small.txt

除了大约一半的嵌套循环之外，这几乎是无趣的。我尝试使用 numpy 对其进行矢量化，但考虑到矩阵/二维数组在每次迭代中都会发生变化，我不太确定该怎么做。

如果有人对我需要做的事情或什至要阅读的内容有任何想法，那将在我的道路上对我有所帮助，那就太棒了。

===================

我写了一个更新版本来考虑 Jaime 的评论：

=================

这次使用矢量化的另一个新版本：

我知道贝尔曼-福特算法适用于有向图。它适用于无向图吗？似乎对于无向图，它将无法检测循环，因为平行边将被视为循环。这是真的还是假的？可以应用算法吗？

令 G = (V;E) 是一个有向图，其边都具有非负权重。设 s,t 是 V 中的 2 个顶点，设 e 是 E 中的一条边。描述一种算法，该算法确定从 s 到 t 的所有最短路径是否包含边 e。

好吧，这就是实现 Dijsktra 时间复杂度的方法：只需从 s 运行 Dijkstra 并计算 delta(s,t)（从 s 到 t 的最短路径的权重）。删除边 e，然后从新图中的 s 再次运行 Djikstra。如果新图中的 delta(s,t) 增加了，则说明从 s 到 t 的所有最短路径都包含边 e，否则不成立。

我想知道是否有更有效的算法来解决这个问题。你认为有可能打败 Dijkstra 的时间复杂度吗？

提前致谢

假设我们想使用 Bellman-Ford 来最小化 max_i x_i - min_i x_i

在变量 x_1, x_2, ... x_n 上（变量的总数 n）

服从 x_i - x_j <= c_{i,j} 形式的 m 个约束

其中 c_{i,j} 是一个可以为负数的指定常数。

我如何证明 Bellman-Ford 可以在 O(n*m) 时间内解决此类问题？

我尝试了以下方法：

为每个变量 x_i 创建一个节点 i

创建一个源节点 s

创建从 s 到所有其他节点的 0 权重边

不知道在此之后该怎么办...请帮助，谢谢。

下面的示例包含一个负循环，但程序似乎没有找到它。有人可以指出什么是错的吗？如果存在负循环，它应该打印出一个负循环，但程序没有做预期的事情。

我知道检查加权有向图的给定边是否属于负循环的问题是 NP 完全的（找到包含所有负循环的最小子图）并且 Bellman-Ford 允许在 O( |V|*|E|) 时间。但是如果我想找到所有属于负循环的顶点呢？我想知道它是否可以比 Floyd-Warshall 的 O(|V|^3) 更快。

我的讲师提到了这一点：

• 尝试减少循环1 的一次迭代的运行时间：只考虑可能提供有效松弛操作的边。

• 如果自上次 d[v] 减小后从 v 发出的边没有松弛，则顶点 v 处于活动状态。

• 仅对从活动顶点传出的边执行 RELAX。

• 将活动顶点存储在队列数据结构中。

我的问题是，FIFO 队列如何加速 Bellman-Ford 的迭代？你在什么情况下“排队”？