最短路径算法加速技术研究综述

被引：77

作者：

宋青

汪小帆

机构：

[1] 上海交通大学电子信息与电气工作学院

来源：

电子科技大学学报 | 2012年 / 41卷 / 02期

关键词：

启发式; 分层; 大规模网络; 最优化; 最短路径;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

最短路径的快速有效计算研究具有重要的实际意义。经典算法的高计算复杂度制约了其在大规模网络中的应用。该文从以优先队列为代表的基本加速技术、目标引导技术以及分层技术3个方面综述了该领域最新、最具代表性的一些算法,包括作者在网络分层模型的构造及其分层搜索算法设计方面的最新成果。最后展望了该领域的未来研究方向。

引用

页码：176 / 184

页数：9

共 9 条

[1]

Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm.[J].Reinhard Bauer;Daniel Delling;Peter Sanders;Dennis Schieferdecker;Dominik Schultes;Dorothea Wagner.Journal of Experimental Algorithmics (JEA).2010,

[2]

Geometric containers for efficient shortest-path computation.[J].Dorothea Wagner;Thomas Willhalm;Christos Zaroliagis.Journal of Experimental Algorithmics (JEA).2005,

[3]

Shortest paths algorithms: Theory and experimental evaluation [J].