Integer priority queues with decrease key in constant time and the single source shortest paths problem

ABSTRACT

We consider Fibonacci heap style integer priority queues supporting insert and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys support delete in O(log log n) time. If the integers are in the range [0,N), we can also support delete in O(log log N) time.Even for the special case of monotone priority queues, where the minimum has to be non-decreasing, the best previous bounds on delete were O((log n)^1/(3-ε)) and O((log N)^1/(4-ε)). These previous bounds used both randomization and amortization. Our new bounds a deterministic, worst-case, with no restriction to monotonicity, and exponentially faster.As a classical application, for a directed graph with n nodes and m edges with non-negative integer weights, we get single source shortest paths in O(m+n log log n) time, or O(m+n log log C) if C is the maximal edge weight. The later solves an open problem of Ahuja, Mehlhorn, Orlin, and Tarjan from 1990.

REFERENCES

• 1: Ravindra K. Ahuja , Kurt Mehlhorn , James Orlin , Robert E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM (JACM), v.37 n.2, p.213-223, April 1990 [doi>10.1145/77600.77615]
• 2: A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
• 3: A. Andersson and M. Thorup. Dynamic ordered sets with exponential search trees. Technical Report cs.DS/0210006, The Computing Research Repository (CoRR), 2002. http://arXiv.org/abs/cs.DS/0210006.
• 4: Paul Beame , Johan Hastad, Optimal bounds for decision problems on the CRCW PRAM, Journal of the ACM (JACM), v.36 n.3, p.643-670, July 1989 [doi>10.1145/65950.65958]
• 5: Boris V. Cherkassky , Andrew V. Goldberg , Craig Silverstein, Buckets, Heaps, Lists, and Monotone Priority Queues, SIAM Journal on Computing, v.28 n.4, p.1326-1346, Aug. 1999 [doi>10.1137/S0097539796313490]
• 6: L. J. Comrie. The hollerith and powers tabulating machines. Trans. Office Machinery Users' Assoc., Ltd, pages 25--37, 1929-30.
• 7: D.V. Denardo and B.L. Fox. Shortest-route methods 1: Reaching, pruning, and buckets. Oper. Res., 27:161--186, 1979.
• 8: Robert B. Dial, Algorithm 360: shortest-path forest with topological ordering [H], Communications of the ACM, v.12 n.11, p.632-633, Nov. 1969 [doi>10.1145/363269.363610]
• 9: E. W. Dijkstra. A note on two problems in connection with graphs. Numer. Math., 1:269--271, 1959.
• 10: James R. Driscoll , Harold N. Gabow , Ruth Shrairman , Robert E. Tarjan, Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation, Communications of the ACM, v.31 n.11, p.1343-1354, Nov. 1988 [doi>10.1145/50087.50096]
• 11: A. I. Dumey. Indexing for rapid random access memory systems. Computers and Automation, 5(12):6--9, 1956.
• 12: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 13: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 14: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 15: Torben Hagerup, Improved Shortest Paths on the Word RAM, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.61-72, July 09-15, 2000
• 16: Yijie Han, Deterministic sorting in O(nlog log n) time and linear space, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509993]
• 17: Yijie Han , Mikkel Thorup, Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.135-144, November 16-19, 2002
• 18: IEEE. Standard for binary floating-point arithmetic. ACM Sigplan Notices, 22:9--25, 1985.
• 19: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 20: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 21: Rajeev Raman, Recent results on the single-source shortest paths problem, ACM SIGACT News, v.28 n.2, p.81-87, June 1997 [doi>10.1145/261342.261352]
• 22: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 23: Mikkel Thorup, On RAM Priority Queues, SIAM Journal on Computing, v.30 n.1, p.86-109, 2000 [doi>10.1137/S0097539795288246]
• 24: Mikkel Thorup, Equivalence between Priority Queues and Sorting, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.125-134, November 16-19, 2002
• 25: P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett., 6(3):80--82, 1977.
• 26: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Syst. Theory, 10:99--127, 1977.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Fibonacci heaps, priority queues, single source shortest paths