我偶然发现了我最初从Wikipedia获得的著名 Yen 对 Bellman-Ford 算法的优化，然后我在练习部分的几本教科书中发现了相同的改进（例如，这是 Cormen 中的问题 24-1 和Sedgewick 中的Web 练习 N5 ）算法”）。
这是改进：
Yen 的第二个改进首先在所有顶点上分配一些任意线性顺序，然后将所有边的集合划分为两个子集。第一个子集 Ef 包含满足 i < j 的所有边 (vi, vj)；第二个，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 在 1 到 n-1 的范围内，E={(i, i+1)}）。在这种情况下，前向顶点集等于 E (E_f = E)，而后向顶点集只是空集。算法的每次迭代仅添加一个正确计算的距离，因此算法在 n-1 时间内完成，这与建议的边界 n/2 相矛盾。
我究竟做错了什么？
UPD：所以这个错误非常愚蠢。我没有考虑通过顶点的迭代，而是将迭代视为路径成本的即时更新。我不会删除这个话题，因为有人赞成它，以防这种改进对某人来说很有趣。