Correctness of Yen's optimization of Bellman-Ford algorithm

Question

I am trying to solve the problem 24-1 of introduction to algorithms, It refers to the Yen's optimization of Bellman-Ford algirithm, I find the introduction in 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.

Unfortunately, I can't prove that how the method that can make at least two edges relax distances match the correct shortest path distances: one from Ef and one of Eb.

shawn shawn · Accepted Answer · 2016-11-24T18:33:14

Ef and Eb are acyclic with topological sort.

Let's prove the Upper bound of main loop is |V|/2

For all vertices v, there are two options for shortest distance from source s. One is d[s,v] = INFINITE, another is d[s,v] = FINITE. Thus, we need to consider the case d[s,v] is finite, which means there must exist some shortest path from s to v.

Let suppose p = (v0,v1,v2,....,vk-1,vk) is that path, where vo = s and vk = v. Let us consider how many times there is a change in direction in p, that is, a situation in which (vi-1,vi) belongs to Ef and (vi,vi+1) belongs to Eb. Based on the proof of Lemma 24.2, p has at most |V|-1 edges. Therefore there are at most |V|-2 changes in direction. Because Ef and Eb are topological sort, any portion of the path where there is no change in direction can be computed with the correct d values in the first or second half of a single pass once the node that begins the no-change-in-direction sequence has the correct d value. Each change in directions requires a half pass in the new direction of the path.

    |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.

Correctness of Yen's optimization of Bellman-Ford algorithm

1 Answers