我的讲师提到了这一点：
• 尝试减少循环1 的一次迭代的运行时间：只考虑可能提供有效松弛操作的边。
• 如果自上次 d[v] 减小后从 v 发出的边没有松弛，则顶点 v 处于活动状态。
• 仅对从活动顶点传出的边执行 RELAX。
• 将活动顶点存储在队列数据结构中。
我的问题是，FIFO 队列如何加速 Bellman-Ford 的迭代？你在什么情况下“排队”？
问问题
2008 次
1 回答
1
队列存在只是因为它是一种方便的数据结构来跟踪活动节点。
当您第一次尝试放松连接到该节点的边时，您将一个节点排入队列。当您到达该节点时，您将放松从活动邻居到该节点的所有边。
执行这些步骤会将 Bellman-Ford 算法转换为更接近Dijksta 算法的算法。
如果节点是活动的，它是下一个考虑。您还访问了节点，您已经确定了您需要了解的所有内容。尚未到达的节点是未访问的。
您可以将这三种状态视为颜色。您开始时仅将初始节点着色为活动状态，而其他所有内容均未访问。随着您的移动，活动颜色将向外移动，形成围绕已访问节点的边界。当您没有更多活动节点时，您就完成了，并且所有内容都已访问。
作为队列的替代方案，您可以使用两个列表。第一个包含您当前正在考虑的活动节点，以及您放入第二个列表的任何新活动节点。第一个列表用完后，将其清空，然后交换两个列表。相反，使用单个队列，您可以将迭代混合在一起，因为当前迭代和下一个迭代之间没有明显的边界。
于 2013-05-25T09:33:57.050 回答