The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges.

Since $E \sim V^2$, is the runtime $O((V+V^2)\log V)$?

  • $\begingroup$ This question is really about how to properly (ab)use Landau notation. Yes, corner cases aside this kind of substitution "works" (and is, by the way, really the only way to make sense of Landau notation with multiple variables if you use the common definition). $\endgroup$ – Raphael Jul 2 '16 at 9:43

The runtime of Dijkstra's algorithm (with Fibonacci Heaps) is $O(|E|+|V|\log|V|)$, which is different from what you were posting.

If $|E|\in \Theta(|V|^2)$, that is your graph is very dense, then this gives you runtime of $O(|V|^2+|V|\log|V|)=O(|V|^2)$. A better runtime would be "surprising", since you have to look at every edge at least once.

When using binary heaps, you get a runtime of $O((|E|+|V|)\log|V|)$ which for $|E|\in \Theta(|V|^2)$ gives $O(|V|^2\log |V|)$.

| cite | improve this answer | |
  • $\begingroup$ Yes, I posted the runtime for a binary heap. $\endgroup$ – Quaxton Hale Jul 2 '16 at 8:08

You can also get rid of the log factor in dense graphs, and do it in $O(V^2)$. See here.

They might give you around $V=5000$ nodes but $O(V^2) = O(2.5 \cdot 10^7)$ edges which will give the leading edge over normal $O(E\log V)$ Dijkstra.

| cite | improve this answer | |
  • $\begingroup$ Please don't use Twitter shortcuts. This website is long form. $\endgroup$ – Yuval Filmus Jan 26 '17 at 12:16
  • 2
    $\begingroup$ Also, can you say something about the other algorithm? Consider what happens if the linked blog disappears. $\endgroup$ – Yuval Filmus Jan 26 '17 at 12:16
  • $\begingroup$ $O(V^2)\neq O(2.5\cdot10^7)=O(1)$. $\endgroup$ – David Richerby Jan 26 '17 at 17:03
  • $\begingroup$ That link only works for a special kind of graph, where the edge weights come from a set of 2 possibilities. That's not what the question was asking about. Also, we discourage link-only answers, where all of the substantive content is in the link. We want answers here to be self-contained, so that the answer remains useful even if the link stops working, and so we don't devolve to just a link farm. $\endgroup$ – D.W. Jan 26 '17 at 17:36

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.