Faster Algorithms for the Shortest Path Problem

Ravindra K. Ahuja, Kurt Mehlhorn, James Orlin, Robert E. Tarjan

Research output: Contribution to journalArticle

295 Scopus citations

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 O1990. 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].

Original languageEnglish (US)
Pages (from-to)213-223
Number of pages11
JournalJournal of the ACM (JACM)
Volume37
Issue number2
DOIs
StatePublished - Jan 4 1990

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Faster Algorithms for the Shortest Path Problem'. Together they form a unique fingerprint.

  • Cite this