# Proof of Dijkstra Algorithm Optimality

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.