Access Restriction

Author Thorup, Mikkel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword RAM algorithms ♦ Shortest paths
Abstract The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph $\textit{G}$ with a source vertex $\textit{s},$ find the shortest path from $\textit{s}$ to all other vertices in the graph.Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from $\textit{s}.$ Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from $\textit{s}.$ However, we do not know how to sort in linear time. Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 46
Issue Number 3
Page Count 33
Starting Page 362
Ending Page 394

Open content in new tab

   Open content in new tab
Source: ACM Digital Library