Fibonacci heaps and their uses in improved network optimization algorithms

Analysis

Why This Paper Matters

This paper is a cornerstone in the field of data structures and graph algorithms. It introduces Fibonacci heaps, a priority queue that achieves optimal amortized time bounds for key operations, particularly the decrease-key operation, which is critical for many network optimization algorithms. The paper's significance lies not only in the new data structure but also in demonstrating its power by improving the running times of several classic problems, including single-source shortest paths, all-pairs shortest paths, the assignment problem, and minimum spanning trees.

The improvements are asymptotic and apply to graphs of appropriate densities, making the results theoretically important. The minimum spanning tree bound of O(m β(m,n)) is particularly striking, as it nearly matches the linear-time lower bound for many practical cases. This work has inspired a long line of research on priority queues and has been a standard reference in algorithm courses and textbooks.

Technical Contributions

• Fibonacci Heaps: A new heap structure that extends binomial queues with lazy melding and a sophisticated consolidation scheme. It supports insert, merge, and decrease-key in O(1) amortized time, and delete-min in O(log n) amortized time.
• Amortized Analysis: The paper uses potential functions to prove the amortized time bounds, introducing the concept of marking nodes to maintain the heap's structure.
• Application to Network Algorithms: The authors apply F-heaps to improve the running times of Dijkstra's algorithm for single-source shortest paths, Floyd-Warshall-like algorithms for all-pairs shortest paths, the Hungarian method for assignment, and Prim's algorithm for minimum spanning trees.
• New Bounds: The paper provides concrete worst-case bounds for each problem, showing improvements over previous results.

Results

The paper reports the following worst-case time bounds, where n is the number of vertices and m the number of edges:

• Single-source shortest path: O(n log n + m), improved from O(m log(m/n+2) n).
• All-pairs shortest path: O(n^2 log n + nm), improved from O(nm log(m/n+2) n).
• Assignment problem: O(n^2 log n + nm), improved from O(nm log(m/n+2) n).
• Minimum spanning tree: O(m β(m,n)), improved from O(m log log(m/n+2) n), where β(m,n) = min{i | log^(i) n ≤ m/n}. For m ≥ n, β(m,n) ≤ log* n.

These results are asymptotic and show improvements for graphs of appropriate densities, with the minimum spanning tree bound being the most dramatic.

Significance

The introduction of Fibonacci heaps has had a lasting impact on algorithm design. It provided a theoretical foundation for efficient priority queues and influenced the development of other data structures like pairing heaps and relaxed heaps. The improved bounds for network optimization problems have been incorporated into standard algorithm references and have guided research on faster graph algorithms. While the constant factors and practical performance of Fibonacci heaps are often not competitive with simpler heaps, the theoretical insights have been invaluable. The paper remains a classic example of how a data structure can drive algorithmic improvements across multiple domains.