Problem Detail: 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|^2log |V|)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/60222 3.2K people like this
