具有FIFO队列的Bellman-Ford如何加速其迭代？
我的讲师提到：
尝试减少循环1一次迭代的运行时间：只考虑可能给出有效松弛操作的边缘。
•如果自上次减少d[v]以来，从v引出的边尚未松弛，则顶点v处于活动状态。
•仅对从活动顶点引出的边执行“松弛”。
•在队列数据结构中存储活动顶点。
我的问题是，FIFO队列如何加速Bellman Ford的迭代？你在什么情况下“排队”？
共有1个答案
队列之所以存在，只是因为它是跟踪活动节点的方便数据结构。
首次尝试松弛连接到某个节点的边时，可以将该节点排队。当您到达该节点时，您将已将活动邻居的所有边松弛到该节点上。
执行这些步骤将贝尔曼-福特算法转化为更接近Dijksta算法的东西。
若节点处于活动状态，那个么它将是下一个需要考虑的节点。您还访问了节点，您已经确定了需要了解的所有内容。尚未到达的节点是未访问的。
您可以将这三种状态视为颜色。开始时，只将初始节点着色为活动节点，其他所有节点均不可见。随着移动，活动颜色将向外移动，形成围绕所访问节点的边界。当您没有更多活动节点，并且所有内容都已着色时，就完成了此操作。
作为队列的替代方案，您可以使用两个列表。第一个包含您当前正在考虑的活动节点，以及您放入第二个列表中的任何新活动节点。第一个列表用完后，将其清空，然后交换两个列表。而是使用单个队列，通过在当前迭代和下一个迭代之间没有明显的边界，将迭代混合在一起。
-
我在试图理解这个算法是如何工作的。 给定一个问题，搜索从源s到图中所有顶点的路径， 我想我必须这样做： 我的问题是: 我的程序是好的还是我必须改变它。 当我必须检查是否存在负循环时？非常感谢。
-
有了贝尔曼-福特的算法，稍有改变：在第7行，我们把
-
我们正在使用AMAZON SQS FIFO队列来处理我们应用程序的预约服务。一旦消息进入队列，它就会触发Amazon Lambda函数来管理预订过程。因为它是一个FIFO队列，所以我们确保如果有2个人请求相同的插槽，那么这个插槽将给第一个请求者。我的问题是：是否有一种方法（也许是SQS FIFO队列中的设置？）这确保了在前一条消息执行完毕之前，一条消息不会触发Amazon Lambda函数。我只是
-
我正在做一个有向图的项目，其中边的权重都依赖于变量x。我试图找到x的最小值，这样我的图就不包含任何正权重的回路。 我的问题是——这可能很愚蠢，但我不明白如何——：我如何使用改良的贝尔曼-福特来检查正电路而不是负电路的存在？ 谢谢。
-
我对贝尔曼-福特做了一点修改，这样它只能“有用”放松。也就是说，d（v）的松弛被更新了。 现在，如果所有最短路径最多有k条弧。那么最坏情况下的运行时是O（V*k），因为在这个智能版本中我们只经过k个弧。这比原来的O（V*E）快一点，因为| k| 有谁能告诉我一种图的类型，这种改进的版本并不比原来的Bellman-Ford算法好？也就是说，最佳情况下的性能是O（V*E）
-
假设有一个具有