Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths

Sunny Atalig, Alexander Hickerson, Arrdya Srivastav +2

We consider the classical single-source shortest path problem in directed weighted graphs. D.~Eppstein proved recently an $\Omega (n^3)$ lower bound for oblivious algorithms that use rel…