复杂网络中最短路径算法的研究及应用

本文将复杂网络中最短路径算法引入到交通网络领域中,将标号改正算法应用于交通网络路径分析.首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法--基于逼近桶结构、改进四叉堆的Dijkstra算法(DIKBA与DIKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比实验.实验结果表明:标号改正算法和标号设定算法优点各异;由于交通网络中路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力.

Research on algorithm for detecting shortest path in complex network and its application

This paper introduces shortest path finding of complicated networks into GIS network research.Labeling algorithms have got broad applications for shortest path finding in complicated networks.After detailed discussion on the structures of labeling algorithms,the implementation,complexity and applicability of labeling setting and label correcting algorithms are analyzed.Then three best-known fastest label algorithms,i.e.,Dijkstra algorithm implemented with approximate buckets (DIKBA),Dijkstra's algorithm based on quad-heap priority queue (DIKQH) and Pallottino algorithm (TWO-Q) ,were used to carry out practical evaluation on three real urban road networks.The results showed that for one-to-one shortest path calculation,DIKQH and DIKBA greatly outperformed than TWO-Q algorithm,and DIKQH exhibited the best running efficiency.For one-to-all shortest path calculation,however,TWO-Q algorithm runs a little faster than DIKQH and DIKBA on the selected real road networks.The author argued that more attention should be paid to TWO-Q algorithm for its efficiency and applicability.