Chuan-xiang REN, Xin-gang HAO, Ying-rui WANG, Guang-hui PAN
College of Information and Electrical Engineering, Shandong University of Science and Technology, Qingdao 266510, China
Abstract—Dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional Dijkstra algorithm, on account of the insufficiency of this algorithm in path optimization, this paper uses adjacency list and circular linked list with combination to store date, and through the improved quick sorting algorithm for weight sorting, accomplish a quick search to the adjacent node, and so an improved Dijkstra algorithm is got. Then apply it to the optimal path search, and make simulation analysis for this algorithm through the example, also verify the effectiveness of the proposed algorithm.
Keywords—route optimization; Dijkstra algorithm; fast sorting algorithm; adjacency list and circular linked list
Manuscript Number: 1674-8042(2010)supp.-0199-04
dio: 10.3969/j.issn1674-8042.2010.supp..52
References
[1]BENJAMIN F Z, 1997. Three Fastest Shortest Path Algorithms on Real Road Networks. Journal of Geographic Information and Decision Analysis, 1(1):69-82.
[2]G. Ausiello, G.F. Italiano, A. Marchetti-Spaccamela, and U. Nanni, 1991. Incremental algorithms for minimal length paths. Journal of Algorithms, 12(4):615–38.
[3]S. Baswana, R. Hariharan, and S. Sen, 2002. Improved decremental algorithms for transitive closure and all-pairs shortest paths. In Proc. 34th ACM Symposium on Theory of Computing (STOC’02), p. 117-123.
[4]Zhang Linguang, 2007. An Improved Dijkstra Algorithm Based on Pairing Heap. Journal of Imaging and Graphics, 5(12): 922-924.
[5]Yan Weimin and Wu Weimin,1996. Data Structure. Beijing: Tsinghua University Press.
[6]Schulz, F., D. Wagner and K. Weihe, 2000. Dijkstra's algorithm on-line: An empirical case study from public railroad transport, Journal of Experimental Algorithmics 5.
[7]Pu Zaiyi and Ren Jianjun, 2003. Implementing of the Shortest Path's Dijkstra by Mark-Method. Journal of Sichuan Teachers College (Natural Science), (24): 52-54.
[8]Wang Zhihe and Ling Yun, 2007. The Optimization and Implementation of the Shortest Path Dijkstra Algorithm. Control &Automation, 11(3).
[9]I. Chabini, 1997. A new shortest path algorithm for discrete dynamic networks. Proceedings of the 8th IFAC Symposium on Transport Systems, Chania, Greece, June 16-17, 551-556.
[10]liu Xin and He Jiannong,2007. Improved Algorithm About Searching for Shortest Path over Traffic Network. Computer Engineering and Applications, 43(14):220-222.
[11]Zhang Jinming, Hong Gang, Wen Rui, Wang Xuetao, 2009. Optimization Strategies of the Dijkstra's Shortest Route Algorithm. Science of Surveying and Mapping, (34)5.
[full text view]
