Faster algorithms for the shortest path problem

ABSTRACT

Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap, is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C, a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O(m + n log C). A two-level form of radix heap gives a bound of O(m + n log C/log log C). A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of O(m + na @@@@log C). The best previously known bounds are O(m + n log n) using Fibonacci heaps alone and O(m log log C) using the priority queue structure of Van Emde Boas et al. [ 17].

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: CARTER, J. L., AND WEGMAN, M.N. Universal classes of hash functions. J. Comput. Syst. Sci. 18 (1979), 143-154.
• 3: DENARDO, E. V., AND FOX, B.L. Shortest-route methods: 1. Reaching, pruning, and buckets. Oper. Res. 27 (1979), 161-186.
• 4: 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]
• 5: DIETZFELBINGER, M., KARLIN, A., MEHLHORN, K., MEYER AUF DER HEIDE, F., ROHNERT, H., AND TARJAN, R. Dynamic perfect hashing: Upper and lower bounds. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1988, pp. 524-531.
• 6: DIJKSTRA, E.W. A note on two problems in connexion with graphs. Numer. Math. 1 (1959), 269-27 I.
• 7: 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]
• 8: 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]
• 9: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 10: JOHNSON, D. B. Efficient special-purpose priority queues. In Proceedings of the 15th Annual Allerton Conference on Communications, Control, and Computing (1977), pp. 1-7.
• 11: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 12: PETERSON, G.L. A balanced tree scheme for meldable heaps with updates. Tech. Rep. GIT-TCS- 87-23. School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Ga., 1987.
• 13: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 14: TARJAN, R. E. Amortized computational complexity. SIAM J. Alg. Discrete Meth. 6 (1985), 306-318.
• 15: Robert Endre Tarjan , Andrew Chi-Chih Yao, Storing a sparse table, Communications of the ACM, v.22 n.11, p.606-611, Nov. 1979 [doi>10.1145/359168.359175]
• 16: VAN EMDE BOAS, P. Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett. 6 (1977), 80-82.
• 17: VAN EMDE BOAS, P., KAAS, R., AND ZIJLSTRA, E. Design and implementation of an efficient priority queue. Math. Syst. Theory 10 (1977), 99-127.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Design, Theory