Dijkstra最短路径算法优化.pdfVIP

25 3 Vol. 25 No. 3 2006 8 Journal ofN anchang Institute ofTechnology Aug. 2006 : 1006- 4869( 2006) 03- 0030- 04 Dijkstra 章永龙 ( , 225009) : 传统 D ijkstra算法在求解节点间最短路径时, 对已标识节点以外的大量节点进行了计算,从而影 了算法 的速度. 在对传统 D ijkstra算法分析的基础上, 对其进行了优化,优化算法只对最短路径上节点的邻居做了处理,而 不涉及到其他节点. 因此,在优化算法中计算的节点数大幅减少,提高了算法的速度. : 最短路径; Dijkstra算法; 优化 : TP301. 6 : A Optim ization of D ijkstra Algorithm ZHAN Yong-long (College of Information Enginneering, University ofYangzhou, Yangzhou 225009, China) Abstract: When a shortestpath between nodes is searched w ith Dijkstra algorithm, a lot of nodes away from lagged nodes are involved, so that the efficiency of Dijkstra algorithm is low. An optmi ization algo- rithm is presented in this paper based on analysis of Dijkstra algorithm. Only these nodes that theneigh- bor of nodes in the shortestpath areprocessed, and other nodes aren tprocessed. Therefore, the number of processed nodes is largely reduced in the optmi ization algorithm, and efficiency of the optmi ization a-l gorithm is mi proved. K ey words: the shortestpath; Dijkstra algorithm; optmi ization 0 , :. , [ 1] ., Dijkstra (). O(N 2 ); ,(N N ), N , [2- 5] ., Dijkstra , Dijkstra ,, ,. 1 D ijkstra . Dijkstra , , : 2006- 05- 24 : ( 1976- ), , , ,. 3 : D ijkstra 31 , . w s j ; p s j j . S; T j