%0 Journal Article
%T 一种基于双端队列的交通网络最短路径Pallottino优化算法
%A 陈洁
%A 陆锋
%J 中国图象图形学报
%D 2006
%R 10.11834/jig.20060367
%X 最短路径算法是计算机科学与地理信息科学领域的研究热点，而标号算法则是最短路径算法中的重要一族。长期以来，对于最短路径的算法实现，绝大多数都是围绕以Dijkstra算法为核心的标号设定算法来展开，而对标号改正算法的研究与应用却非常少见。为了对交通网络最短路径进行更有效、更快速的计算，通过对标号改正算法思想的深入分析，针对其中最具代表性的Pallottino算法，从存储结构和运行结构两方面进行了算法的优化改进，同时分析了该算法的时间复杂度和空间复杂度，并利用实际的大规模城市交通网络进行了效率测试。结果显示，与目前公认最优的标号设定算法中基于逼近桶结构的Dijkstra算法相比，该改进的标号改正Pallottino算法具有更好的适用性和更高的运行效率，因此在交通网络最短路径分析应用中具有很高的应用价值。
%K 最短路径
%K 标号算法
%K Pallottino算法
%K 优先级队列
%K 复杂度
%U http://www.cjig.cn/jig/ch/reader/view_abstract.aspx?file_no=20060367&flag=1