The paper is composed as follows. S

The paper is composed as follows. Section 2 describes the Bellman–Ford–Dijkstra algorithm. Section 3 analyzes BFD. In Section 4, we discuss the robustness of BFD to some known implementations of BF. Section 5 describes and analyzes versions of BFD adjusted to some variants of the Dijkstra’s algorithm implementing its rounds. In Section 6, we show the tightness of the bounds developed for BFD, and discuss a speeding up idea.In Appendix A, we suggest an improvement of the classic analysis of relaxation-based algorithms. A new, straight- forward proof is presented that any such algorithm running on any graph produces a shortest paths tree. The simpli- fication is achieved by considering the set of back-pointers only from the vertices, for which the tentative distance is already equal to the true one. It is shown directly that the shortest paths tree propagates together with the true dis- tances.