Is Dijkstra faster when using Fibonacci Heap?

user_10766233 0
Viewed 56

Is Dijkstra faster when using Fibonacci heap than with the Binary heap?

I did some experiments implementing Fibonacci heap on my own and using it in Dijkstra, I also checked the ready-to-use Fibonacci heap from fibheap library, but none of the implementations turned out to be faster in finding the shortest path with the use of Binary heap.

Is it possible that I made a mistake on some point or is that possible that Fibonacci heap is actually slower than Binary heap in context of shortest path finding in Dijsktra?

binary-heap shortest-path dijkstra fibonacci-heap
1 Answers

Using a Fibonacci Heap improves the asymptotic runtime of the algorithm. In other words, as your graph grows larger, there will eventually come a point where using a Fibonacci Heap is faster than using a binary heap.

However, the conventional wisdom I've heard is that the graph size required before that happens is so large that, for practical purposes, a binary heap will always be faster.

user_2384190
Related