Yen对Bellman-Ford算法的改进

Question

我曾经在维基百科上得到了著名的Yen对Bellman-Ford算法的优化方法，后来我在几本教材的练习部分也发现了相同的改进（例如，在Cormen的书中，这是一个24-1问题，在Sedgewick的“算法”中是Web exercise N5）。

以下是改进内容：

Yen的第二次改进首先对所有顶点进行任意线性排序，然后将所有边的集合分为两个子集。第一个子集Ef包含所有(i,j)边，其中ij。按照v1、v2、...、v|V|的顺序访问每个顶点，在Ef中松弛该顶点的每条出边。然后按照v|V|、v|V|-1、...、v1的顺序访问每个顶点，在Eb中松弛该顶点的每条出边。算法的主循环的每次迭代（除了第一次）都会向匹配正确的最短路径距离的已松弛边的集合中添加至少两条边：一条来自Ef，一条来自Eb。这种修改将算法的主循环的最坏迭代次数从|V|-1减少到|V|/2。不幸的是，我没有找到这个上界|V|/2的证明，而且似乎我找到了一个反例。我确定我错了，但我看不出具体在哪里。

反例只是一个由1到n标记的路径图，初始顶点为1。（因此，E = {(i，i + 1)}，其中i在范围从1到n-1内）。在这种情况下，正向顶点集等于E（E_f = E），而反向顶点集仅为空集。算法的每次迭代仅添加一个正确计算的距离，因此算法在n-1时间内完成，这与所提出的上界n/2相矛盾。

我做错了什么？

更新：所犯的错误非常愚蠢。我没有考虑通过顶点的迭代，认为迭代即为路径成本的即时更新。我不会删除此主题，因为有人对其进行了投票，在某些情况下，这一改进可能会引起某些人的兴趣。

- Roman Dobrovenskii

Answer 1

这实际上是最佳情况，无论顶点数量如何，都可以在2次迭代中完成。

在纸上绘制迭代或编写代码。第一次迭代将找到所有正确的最短路径。第二次迭代将不会改变任何内容，因为上一次迭代距离发生更改的顶点集为空，算法终止。

“正向”通过松弛Ef边集的顶点将完成所有工作，“反向”运行不会做任何事情，因为Eb是一个空集。

- svinja

---

是的，那只是我的思维僵局：我花了几个小时考虑立即更新所有成本而不是迭代。无论如何，还是谢谢。 - Roman Dobrovenskii

@svinja 为什么没有优化，它会在第一次迭代中找到所有正确的最短路径？如果我们从最后一条边松弛到第一条边，情况就是VE。 - shawn

@shawn，你说得对，我认为我读错了“*顶点从1到n标记，初始顶点为1。 (因此，E={(i, i+1)}，其中i的范围从1到n-1)*” ，好像这意味着边缘恰好按顺序排列(1,2)，(2,3)……但是E={}并没有指示任何排序，只有顶点被正确排序(这只有在Yen的改进中有所帮助)。所以即使没有优化，我们仍然可以像你说的那样以最坏的顺序放松边缘。我删除了那部分。 - svinja

@svinja，我正在尝试证明对B算法的改进，然后我发现了这篇文章。感谢你的回答。 - shawn