That is, the time bound of BFD impr

That is, the time bound of BFD improves upon that of Bellman–Ford in the in-between cases when negative edges exist, but are sparsely dispersed in the graph. A motivation of such input graphs comes naturally from classic, seemingly purely non-negative problem settings, where there are a few special edges in the network. For example, consider the navigation problem of finding a shortest route in a road map. Suppose that a driver chooses a few objects of interest, such as a beautiful view or a good restaurant, and assigns a route cost reduction to visiting each of them. Then, the updated road map can acquire a few negative edges.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.The correctness proof of BFD is a generalization of a widely known correctness proof for Bellman–Ford. In an auxiliary statement (Lemma 3.2), we analyze the general behavior of Dijkstra algorithm in graphs with negative edges. Hence, BFD with its proof may become an instructive supplement to a university course in algorithms.