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

Question

我试图解决算法简介中的问题24-1，它指的是Yen对Bellman Ford algirithm的优化，我在wiki中找到了介绍，改进：

Yen的第二个改进首先在所有顶点上分配一些任意的线性顺序，然后将所有边的集合划分为两个子集。第一个子集Ef包含所有边（vi， vj），使得i

不幸的是，我不能证明至少两个边松弛距离的方法如何匹配正确的最短路径距离：一个来自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

因此，此修改将算法主循环的最坏情况迭代次数从|V|−1减少到|V|/2。