災害救援系統(tǒng)最短路徑算法研究.pdf

1、沈陽建筑大學碩士學位論文災害救援系統(tǒng)最短路徑算法研究姓名：夏杰夫申請學位級別：碩士專業(yè)：計算機應用技術指導教師：宋曉宇2011-02II Abstract 碩士研究生學位論文 Abstract The rescue system requires the rescuers get to the spot with the quickest speed when accident happens, and

2、 one of the key technology in the system is 'the shortest path'. In recent years, Chinese highway transport developed rapidly with the rapid development of society and economy. Especiall

3、y in highway construction, Chinese highway networks have been basically formed through the construction of recent decades. However, when natural disasters happen, obtaining the shortest path of r

4、escue vehicles become more difficult in Chinese because the road status in Chinese is very complex. Basing the developmental actuality and deficiency , this paper investigates the issues of disas

5、ter emergency phase relief vehicle routing choice and reoptimazation. The first of this paper introduce the existing shortest path algorithm and all these algorithm be summarized and compared. O

6、n the basis of the existing algorithms, the Dijkstra shortest path algorithm is be selected to apply on the shortest path problem of disaster relief. However, the Dijkstra’ s shortest path alg

7、orithm has great complexity and inefficiency in calculating process. Aiming on the above defects, the algorithm is be improved on the data structure. The improved Dijkstra’ s shortest path algor

8、ithm use min- heap to reduce compute time It can be conclude by the simulation that the new Dijkstra’ s shortest path algorithm can get the shortest path more effectively in rescue system. The

9、 efficiency of the improved algorithm is not less than label correcting algorithm in the average time. In particular, the improved algorithm is more effective than the label correcting algorith

10、m when the relief point is not far from the source. So the improved algorithm is more suitable for solving single- source shortest path, for the rescue system to solve the dynamic shortest p

11、ath is also effective. In the second of this paper, the target is to solve the dynamic shortest path in rescue system. The Dijkstra’ s algorithm is used to establish an initial shortest path

12、. Basing on initial shortest path information, a new shortest path can be obtained according to road conditions change. The dynamic shortest algorithm can get the new shortest path correctly a

13、nd effectively. It reduces the time of computing. The new dynamic algorithm can be applied to compute the shortest path in rescue system. Based on the analysis and summarization of existing al

14、gorithlns，this paper p roposes a series of new shortest path algorithm ideas and algorithm theories with practieability as the goal. The algorithms for shortest path are experimentally proved acc