Centre de documentation
scientifique

SPLZ: An efficient algorithm for single source shortest path problem using compression method / Jingwei Sun in Geoinformatica, vol 20 n° 1 (January - March 2016)  

Public [article]  inGeoinformatica > vol 20 n° 1 (January - March 2016) . - pp 1 - 18 Titre : SPLZ: An efficient algorithm for single source shortest path problem using compression method Type de document : Article/Communication Auteurs : Jingwei Sun, Auteur ; Guangzhong Sun, Auteur Année de publication : 2016 Article en page(s) : pp 1 - 18 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique [Termes IGN] chemin le plus court, algorithme du [Termes IGN] compression de données [Termes IGN] réseau routier [Termes IGN] traitement de données localisées Résumé : (auteur) 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. Numéro de notice : A2016-365 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-015-0229-7 En ligne : http://dx.doi.org/10.1007/s10707-015-0229-7 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=81128 [article]