Course contentsShow
← Computer Science
Lesson 974 of 2,87223. Shortest Path AlgorithmsFree lesson

Dijkstra's with Fibonacci Heap

Achieving O(E + V log V) time complexity with Fibonacci heaps for decrease-key operations.

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.