I recall that the quoted time complexity is correct, assuming the queue is a Fibonacci heap.
https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm#CITER...
https://en.m.wikipedia.org/wiki/Dijkstra%27s_algorithm#CITER...
This is because there are much fewer heap.decrease_key operations on average than Dijkstra's worst case analysis suggests. The expected number of heap.decrease_key operations is not large enough to offset the loss in average runtime for the heap.delete_min operation.