Yen 对 Bellman-Ford 算法的改进题解

假设对于 Bellman-Ford 算法按照如下顺序进行松弛操作。为此，我们首先给输入的图𝐺 = (𝑉, 𝐸)上所有点任意指定一个顺序𝑣1, 𝑣2, … , 𝑣|𝑉|，于是 E 上所有的边就可以分为两类 Ef

= {(vi, vj) : i < j} and Eb = {(vi, vj) : i > j}，进而形成G的两个子图𝐺𝑓 = (𝑉, 𝐸𝑓) 和 𝐺𝑏 = (𝑉, 𝐸𝑏)。注意，这里假设 G 中没有点自环，即没有一条边两个端点是一个点。

a) 证 明𝐺𝑓 和 𝐺𝑏 都 是无 环的 ，而 且 拓扑 排序 结果 分别 为 < 𝑣1, 𝑣2, … , 𝑣|𝑉| >和<𝑣|𝑉|, 𝑣|𝑉|−1, … , 𝑣1 >

假设对于 Bellman-Ford 算法按照如下方式进行每一轮的松弛操作。我们首先对 Ef中的边按照其起点在𝑣1, 𝑣2, … , 𝑣|𝑉|中的顺序依次进行松弛，然后对 Eb中的边按照其起点在𝑣|𝑉|, 𝑣|𝑉|−1,… , 𝑣1中的顺序依次进行松弛

b) 证明在上述算法中，如果 G 中没有由 s 可达的负权环路，那么在⌈|𝑉|/2⌉循环

之后对 V 中所有点都有v. d = δ(s, v)

c) 上述算法是否改善了 Bellman-Ford 算法的渐近运行时间？

答案：

a:

反证法。假设𝐺𝑓不是无环的，于是𝐺𝑓是有环的。一个环必须至少有一条边(u, v)其中 u的下标大于 v。这条边不在𝐸𝑓中(根据𝐸𝑓的定义)，与𝐺𝑓有一个环的假设相反。

对𝐺𝑓来说，〈𝑣1, 𝑣2, ⋯ , 𝑣|𝑉|〉是一个拓扑排序，因为根据𝐸𝑓的定义，我们知道所有的边都是从较小的下标指向较大的下标。

𝐸𝑏的证明与上面相似。

b:

对于所有的边v ∈ V，我们知道要么δ(𝑠, 𝑣) = ∞，要么δ(𝑠, 𝑣)是有限的。如果δ(𝑠, 𝑣) = ∞，

那么v. d将是∞的。因此，我们仅仅需要考虑v. d是有限的情况。从 s 到 v 一定有最短路径。假设p = 〈𝑣0，𝑣1，⋯ 𝑣𝑘−1，𝑣𝑘〉是那条最短路径，其中𝑣0 = 𝑠，𝑣𝑘 = 𝑣。现在我们考虑 p 方向改变了多少次，也就是(𝑣𝑖−1，𝑣𝑖) ∈ 𝐸𝑓和(𝑣𝑖，𝑣𝑖+1) ∈ 𝐸𝑏发生多少次。p 中最多有|V| - 1 条边，所以最多有|V| - 2 个方向的变化。路径的任何部分没有改变方向计算正确的 d 值在第一或第二个一半的一次单程的顶点开始在没有改变方向序列正确的 d 值,因为边缘是松弛的方向序列的顺序。每个方向的改变都需要在路径的新方向上进行半遍。下表根据|V| - 1 的奇偶性和第一个边的方向显示了所需的最大遍历数:

在任何情况下,我们需要通过的最大数量是⌈|𝑉|⁄2⌉。

c:

这个计划不会影响算法的渐近运行时间，因为我们只进行行⌈|𝑉|⁄2⌉传递，而不执行|𝑉| − 1，所以仍然是O(V)通道。每个传递仍然需要θ（E）,所以运行时间仍然是 O (VE)