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)$?
Asked By : Quaxton Hale
Answered By : A.Schulz
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|)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/60222
0 comments:
Post a Comment
Let us know your responses and feedback