The Shortest-Path Problem: Analysis and Comparison of Methods
The Shortest-Path Problem: Analysis and Comparison of Methods
复制标题
最短路径问题：方法分析与比较
DOI：
10.1007/978-3-031-02574-7
复制
发表时间：
2014
期刊：
影响因子：
2.3
通讯作者：
Arturo González
中科院分区：
文献类型：
--
作者：
Hector Ortega;D. Ferraris;Arturo González
许多不同领域的应用都需要计算图中两点之间的最短路径。在本文中，我们从经典的Dijkstra算法开始，详细描述了这一最短路径问题，并转向目前应用于道路网络路径选择的更高级的解决方案，包括启发式算法和预计算技术的使用。由于其中几项改进涉及搜索空间的细微变化，因此可能很难从时间或空间要求的角度来评价它们的好处。为了使方法更全面，并便于它们的比较，本书提供了一个作为公共基准的单一案例研究。本文还从定量和定性的角度比较了所描述的方法探索的搜索空间，并分析了针对特定拓扑的不同方法所达到和确定的节点数。
Many applications in different domains need to calculate the shortest-path between two points in a graph. In this paper we describe this shortest path problem in detail, starting with the classic Dijkstra's algorithm and moving to more advanced solutions that are currently applied to road network routing, including the use of heuristics and precomputation techniques. Since several of these improvements involve subtle changes to the search space, it may be difficult to appreciate their benefits in terms of time or space requirements. To make methods more comprehensive and to facilitate their comparison, this book presents a single case study that serves as a common benchmark. The paper also compares the search spaces explored by the methods described, both from a quantitative and qualitative point of view, and including an analysis of the number of reached and settled nodes by different methods for a particular topology.
DOI：
10.1007/978-3-642-15775-2_25
发表时间：
2010-09
期刊：
--
影响因子：
--
作者：
Hannah Bast;Erik Carlsson;Arno Eigenwillig;R. Geisberger;Chris Harrelson;Veselin Raychev;Fabien Viger
通讯作者：
Hannah Bast;Erik Carlsson;Arno Eigenwillig;R. Geisberger;Chris Harrelson;Veselin Raychev;Fabien Viger
DOI：
10.1007/978-3-319-49487-6_2
发表时间：
2016-01-01
期刊：
ALGORITHM ENGINEERING: SELECTED RESULTS AND SURVEYS
影响因子：
--
作者：
Bast, Hannah;Delling, Daniel;Werneck, Renato F.
通讯作者：
Werneck, Renato F.