algorithm - Yen优化Bellman-Ford算法的正确性

Question

我正在尝试解决算法导论的问题24-1，它指的是Yen's optimization of Bellman-Ford algirithm，我在wiki上找到介绍，improvement :

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.

不幸的是，我无法证明可以使至少两条边松弛距离的方法如何匹配正确的最短路径距离:一条来自 Ef，一条来自 Eb。

Answer 1

Ef 和 Eb 是无环的，具有拓扑排序。

让我们证明主循环的上界是|V|/2

对于所有顶点v，到源s的最短距离有两种选择。一个是 d[s,v] = INFINITE，另一个是 d[s,v] = FINITE。因此，我们需要考虑 d[s,v] 是有限的情况，这意味着必须存在从 s 到 v 的最短路径。

假设 p = (v0,v1,v2,....,vk-1,vk) 是那条路径，其中 vo = s 和 vk = v。让我们考虑有多少次方向改变p中，即(vi-1,vi)属于Ef，(vi,vi+1)属于Eb的情况。根据引理 24.2 的证明，p 至多有 |V|-1 条边。因此最多有 |V|-2 次方向变化。因为 Ef 和 Eb 是拓扑排序的，所以一旦节点开始无变化，就可以在单次传递的前半部分或后半部分使用正确的 d 值计算方向没有变化的路径的任何部分方向序列具有正确的 d 值。方向的每次改变都需要在路径的新方向上经过一半。

    |V-1| | first edge direction | passes
    ----- | -------------------- | ------
    even  | forward              | (|V|-1)/2
    even  | backward             | (|V|-1)/2 +1
    odd   | forward              | |V|/2
    odd   | backward             | |V|/2

So this modification reduces the worst-case number of iterations of the main loop of the algorithm from |V| − 1 to |V|/2.