It should be mentioned that there is a wide experimental study on practical shortest paths algorithms, whose running time for reasonable benchmarks is drastically lower than that defined by the known worst case bounds. For example, see [1,3] and references therein. In [3, Section 5.3] a variant of the Bellman–Ford algorithm is mentioned, where at each round the edges are traversed in the order of the values of function d at their initial vertices, which is the same order as that of BFD. However, that variant was rejected there from consideration, for practical running time reasons.