Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing)
I became curious when Wikipedia mentioned it as the 'best known' rather than the 'best possible'. Is a proof of its optimality an open problem?
There is no non-trivial complexity lower bound on any interesting problem. In particular, any algorithm not running in $O(|V|+|E|)$ is not known to be tight. That said, you might be able to show a lower bound in some restricted model, say the decision tree model. For example, it might be possible that any comparison-based algorithm must make $\Omega(|E|+|V|\log|V|)$ comparisons in the worst case, though I am not aware of any such work on the single-source shortest path problem. See also the related question on cstheory.
Another avenue for obtaining conditional lower bounds is accepting some widely believed complexity assumption such as the Exponential Time Hypothesis or some version of the 3SUM hypothesis (whose strongest version was recently disproved by Grønlund and Pettie), though I'm not aware of any such work either in the present case.
