一种基于双端队列的交通网络最短路径Pallottino优化算法

摘要：

最短路径算法是计算机科学与地理信息科学领域的研究热点,而标号算法则是最短路径算法中的重要一族.长期以来,对于最短路径的算法实现,绝大多数都是围绕以Dijkstra算法为核心的标号设定算法来展开,而对标号改正算法的研究与应用却非常少见.为了对交通网络最短路径进行更有效、更快速的计算,通过对标号改正算法思想的深入分析,针对其中最具代表性的Pallottino算法,从存储结构和运行结构两方面进行了算法的优化改进,同时分析了该算法的时间复杂度和空间复杂度,并利用实际的大规模城市交通网络进行了效率测试.结果显示,与目前公认最优的标号设定算法中基于逼近桶结构的Dijkstra算法相比,该改进的标号改正Pallottino算法具有更好的适用性和更高的运行效率,因此在交通网络最短路径分析应用中具有很高的应用价值.

关键词：最短路径、标号算法、Pallottino算法、优先级队列、复杂度

所属期刊栏目：11

分类号：TP302.7;P208(计算技术、计算机技术)

资助基金：中国科学院资助项目40201043;中国科学院知识创新工程项目CXIOG-D04-02

在线出版日期：2006-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：419-424