Upgrading Yen to Bellman Ford

Question

I came across the famous optimization of the Bellman-Ford Algorithm Names that I got from Wikipedia , then I found the same improvement in several tutorials in the Exercise section (for example, this is problem 24-1 in Cormen and Web exercise N5 in Sedgewick "Algorithms ").

Here's the improvement:

The second improvement of the yen first assigns an arbitrary linear order for all vertices, and then splits 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 |, weakening each outgoing edge from this vertex in Ef. Then each vertex is visited in order v | V |, v | V | -1, ..., v1, weakening each outgoing edge from this vertex to Eb. Each iteration of the main loop of the algorithm, after the first, adds at least two edges to the set of edges, the relaxed distances correspond to the correct shortest path distances: one from Ef and one from Eb. This modification reduces the worst number of iterations of the main loop of the algorithm from | V | - 1 to | V | / 2.

Unfortunately, I could not find evidence of this boundary | V | / 2, and, moreover, it seems that I have found a counterexample. I am sure that I am mistaken in this, but I do not understand where exactly.

A counterexample is simply a path graph with vertices labeled from 1 to n and an initial vertex of 1. (So, E = {(i, i + 1)} for i in the range from 1 to n-1). In this case, the set of direct vertices is E (E_f = E), and the set of inverse vertices is simply an empty set. Each iteration of the algorithm adds only one correctly calculated distance, so the algorithm ends n-1 times, which contradicts the proposed coupled n / 2.

What am I doing wrong?

UPD: So the mistake was very stupid. I did not consider iterating through the peaks, thinking of iterations about immediate updates of costs along the way. I am not deleting this topic because someone supported it if this improvement could be interesting to someone.

Answer 1

This is really the best case that ends in 2 iterations regardless of the number of vertices.

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

Fast-forward through the vertices that relax the set of edges Ef will do all the work, and the “reverse” run will do nothing, because Eb is an empty set.