《ResearchontheOpt_省略_orithmofDijkstra_.docx》由会员分享，可在线阅读，更多相关《ResearchontheOpt_省略_orithmofDijkstra_.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 Vol.l Supplement Journal of Measurement Science and Instrumentation 2010 Research on the Optimization and Simulation of the Shortest Path Based on Algorithm of Dijkstra Chuan-xiang REN, Xin-gang HAO, Ying-rui WANG, Guang-hui PAN (College of Information and Electrical Engineering, Shandong Universit
2、y 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 insuff
3、iciency 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. T
4、hen 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. Keywordsroute optimization; Dijkstra algorithm; fast sorting algorithm; adjacency list and circular linked list Manuscript Number: 16
5、74-8042(2010)supp .-0199-04 dio: 10.3969/j.issnl674-8042.2010.supp.52 1 Introduction Along with economic development, social progress, and acceleration of urbanized progress, peoples demands to transportation have been increased and enhanced obviously. The number of mxinicipal transport tool grows r
6、apidly, which initiates a series of, such as traffic jam, traffic accident, and environmental pollution and so on. How to solve these questions has attracted extensive attention of the whole society. The shortest path question is a hot topic to solve these questions at present. Massive domestic and
7、foreign scholars discussed them deeply, and proposed many kinds of algorithms to solve the shortest path question. The better algorithm is as follows ： TQQ(graph growth with two queues), DKA(the Dijkstras algorithm implemented with approximate buckets), DKD(the Dijkstras algorithm implement with dou
8、ble buckets), the TQQ algorithm is based on the chart growth theory, and suitable for calculating the shortest path from simple source point to all the other nodes. DKA and DKD algorithm is based on the Received: 2010-5-25 Corresponding author: Xingang Ha Dijkstra algorithm, which is regarded as the
9、 most perfect algorithm theoretically. DKA and DKD algorithm is the rationale to solve the shortest path question, which suits for calculating the shortest path question between two spots. However, the Dijkstra algorithm has many insufficiencies in computing time and storage space: the counting yiel
10、d and the storage efficiency are quite low. In view of this question, this paper mainly discusses how to make the improvement to the Dijkstra algorithm, and achieve the algorithm optimization. 2 Traditional Dijkstra Algorithm The Dijkstra algorithm is used to calculate the shortest price path from a
11、 source node to other nodes, and it produces the shortest path by the order which increases progressively according to the path length4. This algorithms basic philosophy is: establishing two marked node collections S and V, and V is the node collection which is not marked; when original state, the c
12、ollection in S only contains source node V0, the collection in V contains all nodes besides source node V0. Then adds to node one by one from the collection V to the collection S on the basis of the order which increases progressively according to the path length, the algorithm join a new node Vj in
13、 the collection S every time, and must compare, count and renew the shortest path length value from source node V0 to surplus various nodes in the collection V. Repeatedly, until all nodes in the collection V join completely in the collections561. In the process of according to tracer method7 to rea
14、lize the Dijkstra algorithm, if we use adjacency matrix to store networks topology, the matrix includes massive 0 and , it increases the number of futile cycles and takes the massive spaces in the memory. To a large-scale sparse matrix, the counting yield and the storage efficiency are low. After th
15、e node collection V which is not marked designate next node Vj as the middle node, in the renewal operating process, it needs to scan all nodes which is not connected with node Vj directly, which will severely influence algorithm computation speed. () 200 Journal of Measurement Science and Instrumen
16、tation Supplement 2010 Simultaneously, due to the unmarked node was deposited in the linked list or the array with the disorderly form, if we choose a smallest weight segmental arc but does not take any measure, then we must scan all spots for choosing a smallest weight segmental arc. In the great d
17、ata quantity situation, this is one key factor to restrict computation speed89 3 Algorithm Improvement 3.1 Storage of road network topology relation For the urban road network, the nodes is huge, and it needs to open NxN (N is node number) the storage space if it uses adjacency matrix store road net
18、works topology. At the same time， i lines and j row?s value in the matrix is corresponding to the weight between i and j, and the weight is 0 when the starting point and the end point is the same point; the weight is when two spots does not have the direct path.The matrix includes massive 0 and , in
19、creasing the number of futile cycles and taking the massive spaces in the storage. The counting yield and the storage efficiency are very low to a large-scale sparse chart10. This article uses the adjacency list to store the network topology in order to save the storage space, and store separately t
20、he shortest distance and the forerunner spot from source point to the various fixed-point with one-dimensional array. Simultaneously we use an auxiliary bidirectional circulation linked list to store the adjacent node that remains to be sorted. Like this, when insert, delete or revise adjacent node,
21、 it can reduce the time complexity of algorithm, and make the counting yield improve greatly. 3.2 Fast realization of weight sorting The Dijkstra algorithms key is “choose the s mallest weight segmental arc from the nodes”. F or one node which is not marked, if the weight o f its adjacent node is no
22、t made any treatment, the n it needs to circulate many times and obtain the node of conform requirements, reducing the algor ithms time efficiency, if we carry on sorting to t he related adjacent node according to the weight, we can obtain the node of conform requirements with only a cycle， then the
23、 algorithms time effici ency will be enhanced correspondingly. The traditi onal weight sorting method includes: Williams he ap sort method、 binary tree sort、 fast sort、 Hill sort bubble sort etc11l This article mainly carries on sorting to the weight through the improved f ast sorting algorithm, rea
24、lize to the related adjace nt node optimization, and reduce the algorithms s earch time greatly. Based on the above, in order to make the im provement to the Dijkstra algorithm, and obtain th e improved algorithm, the step is as follows: We let S be the permanent mark node collec tion, Nei is the ad
25、jacency node collection of the nodes that has marked; prev stores the sorting nodes; distj is the shortest path length from sour ce s to the node j; wj is the shortest paths forer unner node from s to the j; dij is the distance fr om node i to node j, 1) Initialization.S=s, prev=Neis, distj=dsj, (i
26、E Nei)， otherwise distj 卜 (i 任 Nei)， Wj=s, 2) The node in Neis stores prev and carrys on sorting, takes the heap top node m, if dsm= dsj, then S=S u m. 3) Renew the adjacency node collection near m, prev=Neim-S, distj= dsj, dsm+dmj, If dsjsm 十dmj， then the forerunner node of wj is m. 4) Search NeiS-
27、S, and store in prve, designate the minimum value of distj in NeiS-S, and store in min S:distm= UAs】 -5distj， S=S Um. 5) If all nodes have marked, then the algorithm terminate, otherwise changes over to the second step and continues to carry out, until all nodes gather in S. 4 Simulation experiment
28、and result analysis Through the simulation testing according to the Shandong Province highway transportation schematic diagram below, and to make comparison with traditional Dijkstra algorithms result, verifying operation efficiency and the practicability of solving path plan question by the improve
29、d Dijkstra algorithm. 4.1 Establish transport network map Database Shandong highway road networks sites are lo gically divided into each one small road section, as shown in Fig. 1. In the figure, the logical stati on includes toll station and flyovers etc. This art icle only enumerates 10 main highw
30、ay crossing to 11 station nodes because the node Nodes are large. We take each nodes serial number， the correspo nding name and the latitude and longitude as the node list data message in the map database, as sh own in Tab. 1 VoLl Chuan-xiang Ren, Xin-gang Hao 201 Fig. 1 Shandong highway road networ
31、k small road section topology structure graph Tab.l Node list in the map database ns from the improved Dijkstra algorithm from JV nan over-bridge station to the Sunshine south stati on, and the virtual red line is the shortest path w hich obtains from the traditional Dijkstra algorith m. In order to
32、 test the efficiency and feasibility of improved algorithm, many arrays are selected h ere to do simulation experiment. Due to the differ ence of the After the node list was established, the path i nformation list will be established. Data messages of road table in map database include serial num be
33、r which paths beginning and end point corresp onding to between two stations route serial numb er that passed through and correto the large amou nt of data in road table. Tab.2 have only listed p artial data message about the path information tab le. Tab.2 Road information list in the map database 4
34、.2 Simulation and analysis After map database was established, we make the simulation experiment of classical Dijkstra al gorithm and the improved Dijkstra algorithm in th e simulation platform. As shown in Fig. 2, the ag gravation red line is the shortest path which obtai Fig. 2 The shortest path s
35、chematic diagram from Jinan over-bridge station to the Sunshine south station Tab.3 Comparison of function between the traditional Dijkstra algorithm and the improved Dijkstra algorithm source point and end point, Tab.3 lists two groups of data, representing the total number of nodes and running tim
36、e from different source point to the end point It turns out that the improved Dijkstra algorit hm reduces the total number of path nodes and (Continued on P.37) Groupin g Test Category The traditional Dijkstra algorithm The improved Dijkstra algorithm improved /traditiona 1 (%) 1 Computing time 269m
37、s 182ms 67.6% total number of nodes of the path 32 25 78.1% Path total mileage 386.76km 357.24km 91.7% 2 computing time 514ms 307ms 59.7% total number of nodes of the path 52 40 76.9% Path total mileage 523.91km 462.70km 88.3% RoadID Start point destination Length(km) 1 1 4 91.8 2 3 4 100.19 3 4 6 6
38、9.49 4 6 7 123.19 5 2 7 110.64 6 7 8 180.53 7 7 12 202.60 8 6 9 58.22 9 6 12 172.2 10 12 14 155.09 NodelD Node name longitude (x) dimension (y) 1 Liaocheng station 115.57 36.26 2 Heze south station 115.26 35.14 3 Dezhou south station 116.17 37.26 4 Jinan over-bridge station 117.00 36.40 5 Binzhou st
39、ation 118.02 37.22 6 Taian west station 117.08 36.11 7 Jining north station 116.33 35.23 8 Zaozhuang station 117.33 34.52 9 Laiwu east station 117.40 36.03 10 Zibo station 118.03 36.48 VoLl Yong-ming Li, Yin-jing Guo 37 48(5). p.686-689. 7 Jianhua Du, Rencheng Zhang. Based on Power Line Carrier Comm
40、unication temperature acquisition system. Instrument Technique and Sensor. 2007(5).p. 31-34. 8 Zhiyong Zhang,Yu Cao,Lizhe Liu. A communication control circuit interference method which against transient. Computer and Network.2001(5). p.49-50,52 22/100 9 Airong Liu,Yinju Lu,Zhencheng Wang. Fast Algor
41、ithm for (From P.201) Running time, that is to say, the improved algorithm can reach the end point by passing fewer nodes, and can tend to the goal point quickly. 5 Go 门 elusions The traditional Dijkstra algorithm is widely used in the route optimization process, but it has limitation in practical a
42、pplication because of its own shortcomings- This paper adopts the way of combination of adjacency list and circular list to store data. At the same time, it uses the improved Quick Sort Algorithm to sort the weight number, realizing the quick research of adjacent nodes and getting the improved Dijks
43、tra algorithm. At last, there is an experiment to show that the improved Dijkstra algorithm not only saves the storage space but also improves the efficiency, so it has certain practical value. 6 Acknowledgements The research is supported by the “Taishan Scholarship” Construction Engineering and Sha
44、ndong Province Graduate Innovative Project (SDYC08011). References 1 BENJAMIN F Z, 1997. Three Fastest Shortest Path Algorithms on Real Road Networks. Journal of Geographic Information and Decision Analysis, l(l):69-82. Serial Communication CRC. Henan University Natural Science. 2007,37(4). P.41820.
45、 10 Huarui Zhang,Hongwen Yang,Weidong HuWenxian Yu. Limited communication method of sensor management. Optics & Control 2007,14(4). p.70-73,81. 11 Hui Wang,Lu Lu. A communication controller of. Firepower and command and control. 2007,32(7). p.30-32 21/100 2 G Ausiello, GF. Italiano, A. Marchetti-Spa
46、ccamela, 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 (ST
47、OC02)， 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. Dijkstras algorithm on-li
48、ne: An empirical case study from public railroad transport, Journal of Experimental Algorithmics 5. 7 Pu Zaiyi and Ren Jianjun, 2003. Implementing of the Shortest Paths Dijkstra by Mark-Method. Journal of Sichuan Teachers College (Natural Science), (24): 52-54. 8 Wang Zhihe and Ling Yun, 2007. The O
49、ptimization 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 Applic