Lower bounds for non-adaptive shortest path relaxation.
D. Eppstein.
arXiv:2305.09230.
Proc. 18th Algorithms and Data Structures Symposium (WADS 2023).
Springer, Lecture Notes in Computer Science 13079 (2023), pp. 416–429, doi:10.1007/978-3-031-38906-1_27.
The Bellman–Ford algorithm for single-source shortest paths operates by relaxation steps, in which it checks for a given edge whether the best path it knows to the start of the edge, plus the edge itself, is better than the path it already knows to the end of the edge. We prove that, up to constant factors, Bellman–Ford is optimal among algorithms that use relaxation in an edge ordering that does not depend on the results of earlier relaxation steps.