Bellman-Ford algorithm's intermediate optimality property, is it correct?

Question

Bellman-Ford algorithm is famously known to solve the single source shortest path problem (SSSPP) for any arbitrary connected graph G(V,E) with additive edge weights, whenever one exists.

The basic implementation version of the algorithm for e.g.: Bellman-Ford-Wiki-page and its proof of correctness, when used parallel relaxation of all edges, as per my understanding, implies an interesting by-product, which I call as "intermediate optimality property", (which might be very helpful for some applications like this question) is stated as below:

After k iterations, we have every node identified with its shortest path from the same source, under the constraint of #edges in the path is <= k

This, under the assumption of simple shortest-path existence, will ensure producing the shortest path solution to SSSPP, for every destination node, after at most |V|-1 iterations.

Is the above property correct?

According to some people (for e.g. comments just below this question), it is not correct and I fail to understand why!!

(UPDATED: I am using a parallel update on all the vertices.)

Answer 1

Suppose we have a simple graph A->B->C->D with all weights equal to 1.

If we visit the vertices in the order A,B,C,D then during the first iteration we will relax all of the following:

A->B, finds shortest path to B is 1
B->C, finds shortest path to C is 2
C->D, finds shortest path to D is 3.

So in the first iteration we have found the shortest path to D despite this path needing 3 edges.

However, if the vertices were visited in the order D,C,B,A it would take more iterations to find the shortest path to D.

In other words, after k iterations we will have certainly found any shortest paths with #edges <= k, however we may also have found a better route that uses more edges.