2
$\begingroup$

I read in my notes:

If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, and if we run Bellman–Ford algorithm $|V|$ times, we get time $O(V^2E)$.

The above details are not important.

I read too, that Dijkstra's algorithm works better for sparse graph, that is, $O(VE+ V^2 \log V)$ is better than $O(V^2E)$ asymptotically for sparse graphs.

I think sparse graphs are graphs satisfying $ |E| = O(V)$ or $E=o(V^2/\log V)$. In fact, I have two misunderstandings:

  1. Which one is more common as the definition of a sparse graph?

  2. According to 1, how we can intuitively understand that $O(VE+ V^2 \log V)$ is better asymptotically than $O(V^2E)$? At least I think the reverse is true.

$\endgroup$
8
  • $\begingroup$ What is the specific doubt you have? If it clear to you how the given time complexity have been obtained (for $E= \Theta(V^2)$ !!) then it should be clear why Dijkstra should be preferred. Notice, however, that these are definitely NOT the best known algorithms to solve APSP in dense graphs. $\endgroup$
    – Steven
    Dec 15 '20 at 16:58
  • $\begingroup$ $V^2 \log V = O(VE)$ as soon as $E = \Omega(V \log V)$. Since we are dealing with dense graphs, this additive term can be safely omitted by Dijkstra's algorithm complexity. Then you are just comparing $\Theta(VE)$ with $\Theta(V^2 E)$. It is immediate that the first complexity is better. $\endgroup$
    – Steven
    Dec 15 '20 at 17:07
  • $\begingroup$ Dense graph is not a formally defined concept. It means a graph with "many edges" compared to the number of vertices. Clearly a graph with $\Theta(V^2)$ edges is dense, but the converse might or might not be true depending on the context. $\endgroup$
    – Steven
    Dec 15 '20 at 17:10
  • 2
    $\begingroup$ $VE$ is obviously better than $V^2 E$, and $V^2 \log V$ is better than $V^2 E$ when $E = \omega(\log V)$, which holds for any reasonable graph. $\endgroup$
    – user114966
    Dec 15 '20 at 18:36
  • $\begingroup$ @Sara, sorry I misunderstood your question. Anyway, Dmitry's comment settles it. $\endgroup$
    – Steven
    Dec 15 '20 at 19:09
2
$\begingroup$

There is no standard definition for sparse graphs. Some common definition include graphs in which $E = o(V^2)$, $E=O(V^{2-\epsilon})$, $E = O(V^{1+\epsilon})$, $E=O(V^{1+o(1)})$, $E = O(V\log^C V)$, and $E = O(V)$.

In most situations, it is safe to assume that the graph is connected, and so $E \geq V-1$. In such cases, $VE + V^2\log V = O(V^2 E)$, and so an upper bound on the running time of the form $O(VE + V^2\log V)$ is better than an upper bound of the form $O(V^2 E)$: indeed, the former implies the latter.

$\endgroup$
3
  • $\begingroup$ The important inequality is $E \geq V-1$. $\endgroup$ Dec 16 '20 at 18:20
  • $\begingroup$ No, because to compare the running times we need a lower bound on $E$, not an upper bound. $\endgroup$ Dec 16 '20 at 19:09
  • $\begingroup$ Yes, that's right. $\endgroup$ Dec 16 '20 at 19:51

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.