This paper introduces Fibonacci heaps (F-heaps), a new data structure for implementing heaps (priority queues). F-heaps extend binomial queues and support arbitrary deletion from an n-item heap in O(log n) amortized time, while all other standard heap operations are performed in O(1) amortized time. The authors demonstrate that F-heaps can significantly improve the running times of several network optimization algorithms. Specifically, they achieve the following worst-case bounds: 1. O(n log n + m) for the single-source shortest path problem with nonnegative edge lengths. 2. O(n² log n + nm) for the all-pairs shortest path problem. 3. O(n² log n + nm) for the assignment problem (weighted bipartite matching). 4. O(mβ(m, n)) for the minimum spanning tree problem, where β(m, n) = min{i | log^i n ≤ m/n}. The most striking improvement is in the minimum spanning tree problem, which is an asymptotic improvement for sparse graphs. The paper also discusses variants of F-heaps and their applications in various network optimization problems, including Dijkstra's algorithm, the all-pairs shortest path problem, and the assignment problem. Additionally, it explores the potential for further improvements in the time bounds for finding shortest paths and minimum spanning trees.This paper introduces Fibonacci heaps (F-heaps), a new data structure for implementing heaps (priority queues). F-heaps extend binomial queues and support arbitrary deletion from an n-item heap in O(log n) amortized time, while all other standard heap operations are performed in O(1) amortized time. The authors demonstrate that F-heaps can significantly improve the running times of several network optimization algorithms. Specifically, they achieve the following worst-case bounds: 1. O(n log n + m) for the single-source shortest path problem with nonnegative edge lengths. 2. O(n² log n + nm) for the all-pairs shortest path problem. 3. O(n² log n + nm) for the assignment problem (weighted bipartite matching). 4. O(mβ(m, n)) for the minimum spanning tree problem, where β(m, n) = min{i | log^i n ≤ m/n}. The most striking improvement is in the minimum spanning tree problem, which is an asymptotic improvement for sparse graphs. The paper also discusses variants of F-heaps and their applications in various network optimization problems, including Dijkstra's algorithm, the all-pairs shortest path problem, and the assignment problem. Additionally, it explores the potential for further improvements in the time bounds for finding shortest paths and minimum spanning trees.