1
$\begingroup$

I read in my notes:

if we use Dijkstra $|V|$ times ($|V|$ number of vertexes) 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 is not important.

I read too, in sparse graph Dijkstra works better (i.e: $O(VE+ V^2 log V)$ is better asymptotic respect to $O(V^2E)$ in sparse graph).

I think sparse graph is $ |E| \in O(V)$ or $E=o(V^2/\log V)$. Infact I have two misunderestanding:

$1)$ which one is used to show a graph is sparse commonly?

$2)$ according to $(1)$ how we can intuitively understand $O(VE+ V^2 log V)$ is better asymptotic respect to $O(V^2E)$ at least I think the reverse is true.

$\endgroup$
1
2
$\begingroup$

As well said by wikipedia The distinction between sparse and dense graphs is rather vague, and depends on the context.

The accepted answer in this StackOverflow question, also state

Dense graph is a graph in which the number of edges is close to the maximal number of edges. Sparse graph is a graph in which the number of edges is close to the minimal number of edges.

Sparse or Dense is not really a proper property of a graph. it will indeed depend on the context. Your two "definitions" are perfectly both acceptable.

For the second point, if you suppose that $E=O(V)$, then

  • Dijkstra works in $O(VE+V^2\log V)=O(V^2+V^2\log V)=o(V^3)$
  • bellman ford works in $O(V^2E)=O(V^3)$

if you suppose that $E=o(V^2/\log V)$, then

  • Dijkstra works in $O(VE+V^2\log V)=o(V^3/\log V)$
  • bellman ford works in $O(V^2E)=o(V^4/\log V)$

So that Dijkstra is more efficient in both cases.

$\endgroup$
0

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.