A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks
A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks
复制标题
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
亚伯拉罕等人。 [SODA 2010] 最近提出了几种实用的点对点最短路径算法的理论分析，该算法基于将道路网络建模为低高速公路维度的图。他们还分析了标记算法。虽然该算法不存在实际实现，但它具有最佳时间限制。本文描述了一种标记算法的实现，该算法比大陆道路网络上任何现有方法都要快。
Abraham et al. [SODA 2010] have recently presented a theoretical analysis of several practical point-to-point shortest path algorithms based on modeling road networks as graphs with low highway dimension. They also analyze alabeling algorithm. While no practical implementation of this algorithm existed, it has the best time bounds. This paper describes an implementation of the labeling algorithm that is faster than any existing method on continental road networks.