Back to Search
Start Over
SPLZ: An efficient algorithm for single source shortest path problem using compression method.
- Source :
-
GeoInformatica . Jan2016, Vol. 20 Issue 1, p1-18. 18p. - Publication Year :
- 2016
-
Abstract
- Efficient solution of the single source shortest path (SSSP) problem on road networks is an important requirement for numerous real-world applications. This paper introduces an algorithm for the SSSP problem using compression method. Owning to precomputing and storing all-pairs shortest path (APSP), the process of solving SSSP problem is a simple lookup of a little data from precomputed APSP and decompression. APSP without compression needs at least 1TB memory for a road network with one million vertices. Our algorithm can compress such an APSP into several GB, and ensure a good performance of decompression. In our experiment on a dataset about Northwest USA (with 1.2 millions vertices), our method can achieve about three orders of magnitude faster than Dijkstra algorithm based on binary heap. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13846175
- Volume :
- 20
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- GeoInformatica
- Publication Type :
- Academic Journal
- Accession number :
- 112084034
- Full Text :
- https://doi.org/10.1007/s10707-015-0229-7