Comparing two algorithms for all-pairs shortest paths

Question

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.

Answer 1

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.