Dijkstra's with Fibonacci Heap
You'll learn: How Fibonacci heaps enable Dijkstra's algorithm to achieve its theoretically best time complexity of O(E + V log V).
Why Fibonacci Heaps Matter for Dijkstra's
In previous lessons, you saw Dijkstra's using arrays (O(V²)) and binary heaps (O((E + V) log V)). The bottleneck? The decrease-key operation—when you discover a shorter path to a vertex and need to update its priority in the queue.
Binary heaps perform decrease-key in O(log V) time, and since we might do this once per edge, we get O(E log V) just from updates. Fibonacci heaps change the game by making decrease-key amortized O(1).
How Fibonacci Heaps Improve Performance
A Fibonacci heap is a complex data structure with lazy operations: updates are deferred until absolutely necessary. When you decrease a key, the heap doesn't immediately restructure—it marks nodes and fixes things later during extract-min operations.
This laziness means:
- Insert: O(1) amortized
- Extract-min: O(log V) amortized (we do this V times = O(V log V))
- Decrease-key: O(1) amortized (we do this at most E times = O(E))
Putting it together: O(V log V) + O(E) = O(E + V log V)
The Practical Reality
Think of it like postponing chores: you save time in the moment (decrease-key), but eventually you must clean up (extract-min does extra work). Over many operations, the savings balance out.
Note: Fibonacci heaps are rarely used in practice—their constant factors and implementation complexity often make binary heaps faster for real-world graphs. They're mainly a theoretical achievement.
Key Takeaway: Fibonacci heaps reduce Dijkstra's time complexity to O(E + V log V) by performing decrease-key operations in amortized constant time, making them theoretically optimal for dense graphs.