algorithm - Yen 对 Bellman-Ford 的改进

Question

我偶然发现了著名的 Yen 对 Bellman-Ford 算法的优化，我最初是从 Wikipedia 得到的。 , 然后我在练习部分的几本教科书中发现了相同的改进(例如，这是 Cormen 中的问题 24-1 和 Sedgewick 的“算法”中的 Web exercise N5)。

这是改进:

Yen's second improvement first assigns some arbitrary linear order on all vertices and then partitions the set of all edges into two subsets. The first subset, Ef, contains all edges (vi, vj) such that i < j; the second, Eb, contains edges (vi, vj) such that i > j. Each vertex is visited in the order v1, v2, ..., v|V|, relaxing each outgoing edge from that vertex in Ef. Each vertex is then visited in the order v|V|, v|V|−1, ..., v1, relaxing each outgoing edge from that vertex in Eb. Each iteration of the main loop of the algorithm, after the first one, adds at least two edges to the set of edges whose relaxed distances match the correct shortest path distances: one from Ef and one from Eb. This modification reduces the worst-case number of iterations of the main loop of the algorithm from |V| − 1 to |V|/2.

不幸的是，我没能找到这个界|V|/2 的证明，而且，我似乎找到了一个反例。我确定我错了，但我看不出确切的位置。

反例只是一个路径图，顶点标记为从 1 到 n，初始顶点为 1。(因此，E={(i, i+1)} for i in range from 1 to n-1)。在那种情况下，前向顶点集等于 E (E_f = E)，而后向顶点集只是空集。算法的每次迭代只增加一个正确计算的距离，因此算法在 n-1 次内完成，这与建议的边界 n/2 相矛盾。

我做错了什么？

UPD:所以这个错误非常愚蠢。我没有考虑通过顶点的迭代，将迭代视为路径成本的立即更新。我不会因为有人赞成它而删除这个主题，以防有人对这种改进感兴趣。

Answer 1

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

在纸上画出迭代或编写代码。第一次迭代将找到所有正确的最短路径。第二次迭代不会改变任何东西，算法终止，因为上次迭代距离改变的顶点集是空的。

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