Non-adaptive Bellman-Ford: Yen's improvement is optimal

Jialu Hu, László Kozma

The Bellman-Ford algorithm for single-source shortest paths repeatedly updates tentative distances in an operation called {relaxing an edge}. In several important applications a {n…