Rom*_*kii 6 algorithm time-complexity bellman-ford
我偶然发现了着名的Yen对Bellman-Ford算法的优化,这是我最初从维基百科得到的,然后我在练习部分的几本教科书中找到了相同的改进(例如,这是Cormen的24-1问题和在Sedgewick的网络练习N5 "算法").
这是改进:
Yen的第二个改进首先在所有顶点上分配一些任意线性顺序,然后将所有边的集合划分为两个子集.第一个子集Ef包含所有边(vi,vj),使得i <j; 第二个,Eb,包含边(vi,vj),使得i> j.按照v1,v2,...,v | V |的顺序访问每个顶点,从Ef中的那个顶点放宽每个输出边缘.然后按照v | V |,v | V | -1,...,v1的顺序访问每个顶点,从Eb中的那个顶点放宽每个输出边缘.算法的主循环的每次迭代,在第一次迭代之后,将至少两个边缘添加到边缘集合,其宽松距离匹配正确的最短路径距离:一个来自Ef,一个来自Eb.这种修改从| V |减少了算法主循环的最坏情况迭代次数 - 1到| V |/2.
不幸的是,我没有设法找到这个绑定| V |/2的证明,而且,似乎我找到了一个反例.我确信我错了,但我看不清楚到底在哪里.
反例只是一个路径图,顶点标记为1到n和初始顶点1.(因此,对于i,E = {(i,i + 1)}的范围从1到n-1).在这种情况下,前向顶点集合等于E(E_f = E),后向顶点集合只是空集合.算法的每次迭代仅添加一个正确计算的距离,因此算法在n-1时间内完成,这与提出的约束n/2相矛盾.
我究竟做错了什么？
UPD:所以这个错误非常愚蠢.我没有考虑通过顶点的迭代,考虑迭代直接更新路径成本.我不是删除这个主题,因为有人对它进行了投票,以防这种改进对某些人来说很有意思.
这实际上是最好的情况，无论顶点数量有多少，都会在 2 次迭代中完成。
在纸上画出迭代或编写代码。第一次迭代将找到所有正确的最短路径。第二次迭代将不会改变任何内容，并且算法终止，因为上次迭代距离发生更改的顶点集为空。
通过松弛 Ef 边集的顶点的“向前”运行将完成所有工作，而“向后”运行不会执行任何操作，因为 Eb 是一个空集。