Yen's improvement to Bellman-Ford

Question

I stumbled with famous Yen's optimization of Bellman-Ford algorithm that I got initially from Wikipedia, then I found the same improvement in several textbooks in Exercise section (for example, this is a problem 24-1 in Cormen and Web exercise N5 in Sedgewick's "Algorithms").

Here's the 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 didn't manage to find the proof of this bound |V|/2, and moreover, it seems that I found a counterexample. I'm sure that I'm wrong about that, but I can't see where exactly.

The counterexample is just a path graph with vertices labeled from 1 to n and initial vertex 1. (So, E={(i, i+1)} for i in range from 1 to n-1). In that case the set of forward vertices is equal E (E_f = E) and the set of backward vertices is just the empty set. Each iteration of algorithm adds only one correctly computed distance, so algorithm finishes in n-1 time, which contradicts the proposed bound n/2.

What am I doing wrong?

UPD: So the mistake was very stupid. I didn't consider the iteration through vertices, thinking about iterations as of immediate updates of path costs. I'm not deleting this topic because someone upvoted it, in case this improvement can be interesting for someone.

Answer 1

This is actually the best case which finishes in 2 iterations regardless of the number of vertices.

Draw the iterations on paper or write the code. The first iteration will find all the correct shortest paths. The second iteration will then not change anything and the algorithm terminates because the set of vertices whose distance was changed last iteration is empty.

The "forward" run through the vertices that relaxes the Ef set of edges will do all the work, while the "backwards" run won't do anything because Eb is an empty set.