SPLZ: An efficient algorithm for single source shortest path problem using compression method
SPLZ: An efficient algorithm for single source shortest path problem using compression method
复制标题
SPLZ：一种使用压缩方法解决单源最短路径问题的高效算法
DOI：
10.1007/s10707-015-0229-7
复制
发表时间：
2014-08
期刊：
影响因子：
2
通讯作者：
Sun, Guangzhong
中科院分区：
文献类型：
--
作者：
Sun, Jingwei;Sun, Guangzhong
道路网络上的单源最短路径（SSSP）问题的有效解决方案是许多现实世界的应用的重要要求。本文介绍了一种利用压缩方法求解SSSP问题的算法。由于预先计算并存储了所有对的最短路径（APSP），求解SSSP问题的过程是从预先计算的APSP中查找少量数据并解压缩。没有压缩的APSP需要至少1TB的内存，用于拥有100万个顶点的道路网络。我们的算法可以将这样一个APSP压缩到几个GB，并保证了良好的解压缩性能。在美国西北部的一个数据集（120万个顶点）上的实验中，我们的方法比基于二进制堆的Dijkstra算法快了大约三个数量级。
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.
登录
查看更多内容
影响因子：
4
作者：
Jagan Sankaranarayanan;H. Alborzi;H. Samet
通讯作者：
Jagan Sankaranarayanan;H. Alborzi;H. Samet
DOI：
10.1090/dimacs/074
发表时间：
2009-07
期刊：
--
影响因子：
--
作者：
C. Demetrescu;A. Goldberg;David S. Johnson
通讯作者：
C. Demetrescu;A. Goldberg;David S. Johnson
DOI：
10.1007/978-3-642-20662-7_20
发表时间：
2011-05
期刊：
--
影响因子：
--
作者：
Ittai Abraham;Daniel Delling;A. Goldberg;Renato F. Werneck
通讯作者：
Ittai Abraham;Daniel Delling;A. Goldberg;Renato F. Werneck
DOI：
10.1016/j.jpdc.2012.02.007
发表时间：
2011-05
期刊：
2011 IEEE International Parallel & Distributed Processing Symposium
影响因子：
--
作者：
Daniel Delling;A. Goldberg;A. Nowatzyk;Renato F. Werneck
通讯作者：
Daniel Delling;A. Goldberg;A. Nowatzyk;Renato F. Werneck
影响因子：
2.1
作者：
E. Dijkstra
通讯作者：
E. Dijkstra