Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Running time of Dijkstra Correction? | Reply
In the tutorial, under the Shortest Paths problem description the running time of Dijkstra is described as O(E*V*Log(V)). This threw me off since I thought the running time was O(E + V*Log(V)). Double checking with some other resources, I think that that is probably what should be used instead. Without using the Fibonacci heap implementation I guess it'd be O(E*Log(V)), but that is still faster than what's in the tutorial. Minor quibble in a very helpful tutorial, but thought I'd just put it out there.
Re: Running time of Dijkstra Correction? (response to post by mailisa) | Reply
After reading your comment , I checked CLRS and found that with Fibonacci Heap the running time is O(VlogV + E)