Dijkstra’s algorithm and the Fibonacci heap
Please do note that, depending on the dataset size, it may be faster to just use a plain old binary heap. In this case, the big O cost for Dijkstra's algorithm is O((E + V) log V), as opposed to the better O(E + V log V) for a Fibonacci heap. Note, also, that Fibonacci heap operations are amortized time, so if you're not operating on a large enough dataset, the costs will not amortize enough and you may end up with a slower real time.<p>A binary heap also has better locality of reference, because you have more chances of a cache hit, especially when you're near the root. The Fibonacci heap, in contrast, keeps a number of pointers to memory locations that are all allocated on-the-go and possibly very far apart. If the binary heap is implemented as a B-heap, as described by PHK [1], it can be made even faster.<p>My point is: please benchmark. Always benchmark. "Stupid" algorithms and data structures may work much better for your case than you would have thought. Programmers are notoriously bad at finding the real bottlenecks... so please benchmark and profile. Fibonacci heaps, AVL trees, KMP, Coppersmith-Winograd, these are all little works of art and theoretically great solutions. With big data, they <i>will</i> perform better than more naive solutions. But that big data doesn't happen as often as you might think. Computers are weird, have too many quirks, and their operation will surprise you, no matter how skilled you are. So profile your programs.<p>[1]: <a href="http://queue.acm.org/detail.cfm?id=1814327" rel="nofollow">http://queue.acm.org/detail.cfm?id=1814327</a>