5 ms·

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#CITEREFFred

• lambo4bkfast 4y ago
  Ah yes you're correct. Fibonacci heap's aren't usually used in most applications of dijkstra's algorithm (such as road networks) though because trading an O(logn) heap.decrease_key operation for an O(1) heap.decrease_key operation, but getting a slower heap.delete_min operation (by a constant factor) isn't worth it. 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.
  • cashweaver 4y ago
    I didn't know that! Thank you for elaborating.