I recently made an initial comparison of the Dijkstra algorithm runtime using two data structures: a Java PriorityQueue (based on a binary heap, if I'm not mistaken) and a Fibonacci heap. I used Java currentTimeMillis () to do my calculations. The results that I have finished are quite interesting. This is the output for one of my test boxes:
Running Dijkstra with 8 nodes and 27 links
- Execution time with binary heap: 1 miliseconds
- Execution time with Fibonacci heap: 4 miliseconds
Admittedly, at the moment I am not well versed in data sets, and the above graph is my biggest (I plan to do it soon). But does that make sense? I always thought that Fibonacci heaps were faster than other data structures due to their amortized runtime compared to other data structures. I’m not quite sure where this 3 millisecond difference comes from. (I run it on an Intel Core Ivy Bridge i7-3630M processor if that helps.)
Note. I came across this thread that could explain this problem, although it is still unclear why the version of the Fibonacci heap takes longer. In accordance with this flow, this may be due to the fact that my schedule is not tight enough, and therefore the number of operations with decreasing the key is not large enough for the performance of the Fibonacci heap to really shine. Will this be the only plausible conclusion, or is there something else I'm missing?
source
share