6
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I'd argue that the lower bound on comparison-based sorting is a non-trivial bound on an interesting problem but I agree with the spirit of what you're saying. $\endgroup$ – David Richerby Nov 18 '14 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.