3
$\begingroup$

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)$?

$\endgroup$
1
  • $\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, 2016 at 9:43

2 Answers 2

5
$\begingroup$

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|)$.

$\endgroup$
1
  • $\begingroup$ Yes, I posted the runtime for a binary heap. $\endgroup$ Jul 2, 2016 at 8:08
-1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Please don't use Twitter shortcuts. This website is long form. $\endgroup$ Jan 26, 2017 at 12:16
  • 2
    $\begingroup$ Also, can you say something about the other algorithm? Consider what happens if the linked blog disappears. $\endgroup$ Jan 26, 2017 at 12:16
  • $\begingroup$ $O(V^2)\neq O(2.5\cdot10^7)=O(1)$. $\endgroup$ Jan 26, 2017 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, 2017 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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