Fingers crossed braindead redditors don't migrate here and ruin this space.
31 karma · joined March 23, 2022
This is akin to blaming a patient for medical malpractice — "why didn't the patient choose a better doctor".
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.
"Two textbook algorithms for SSSP are Bellman-Ford and Dijkstra’s algorithm. Dijkstra’s algorithm is near-linear time (O(m + n log n) time)"
This is incorrect; Dijkstra's Algorithm using a binary priority queue has: O((m + n)log n) time