当前位置: 首页 > 知识库问答 >
问题:

具有FIFO队列的Bellman-Ford如何加速其迭代?

邓季
2023-03-14

我的讲师提到:

尝试减少循环1一次迭代的运行时间:只考虑可能给出有效松弛操作的边缘。

•如果自上次减少d[v]以来,从v引出的边尚未松弛,则顶点v处于活动状态。

•仅对从活动顶点引出的边执行“松弛”。

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

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

共有1个答案

余歌者
2023-03-14

队列之所以存在,只是因为它是跟踪活动节点的方便数据结构。

首次尝试松弛连接到某个节点的边时,可以将该节点排队。当您到达该节点时,您将已将活动邻居的所有边松弛到该节点上。

执行这些步骤将贝尔曼-福特算法转化为更接近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)

  • 假设有一个具有