Fibonacci heap decrease-key and Dijkstra's asymptotic complexity

Dijkstra's algorithm performs V extract-min operations and up to E decrease-key operations (one per edge relaxation that improves a tentative distance). With a binary heap, decrease-key costs O(log V) (a sift-up, typically requiring an auxiliary map from vertex to heap index). With a Fibonacci heap, decrease-key costs O(1) amortized while extract-min stays O(log V) amortized. What is Dijkstra's total complexity with each, and why does the difference matter?

12 of 46 in Data Structures & Algorithms