Dijkstra算法在园区消防车最优路径中的应用.doc

Dijkstra算法在园区消防车最优路径中的应用 　　摘要：本文针对当前园区消防车辆到达受灾点的事故蔓延状况随到达时间的延长而加重的问题，研究并提出了改进的Dijkstra算法。并且通过对传统Dijkstra算法与改进的Dijkstra算法进行比较，得出改进的Dijkstra算法求得的最优路径使消防车到达的时间更短。 　　关键词：园区事故 Dijkstra算法 改进的Dijkstra算法 　　中图分类号：U491.2 文献标识码：A 　　The improved Dijkstra algorithm application in optimal path selection of the campus fire truck 　　ZHANG Tao1，Li De-tang2，Zheng Kai-ju1（1. Ports and transportation engineering college， Zhejiang Ocean University；2. School of Naval Architecture and Mechanical-electrical Engineering， Zhejiang Ocean University、Offshore in Zhejiang 　　province key laboratory of ocean engineering technology Zhoushan 316000，China） 　　Abstract：In allusion to the problem of the current campus fire vehicles arrived at the point of accident along with the extension of time of arrival is aggravating， the research and the improved Dijkstra algorithm are put forward. By comparing traditional Dijkstra algorithm and the improved Dijkstra algorithm， it is concluded that the improved Dijkstra algorithm obtains the optimal path taking less time to make the fire engines arrived. 　　Key Words：The accident of industrial park Dijkstra algorithm The improved Dijkstra algorithm 　　由于全球经济的不断快速发展，园区经济最为促进经济快速增长的重要产业也在发生着巨大的变化。在园区发展过程中难免存在一定的危险源，当危险源在一定环境下会发生事故，在园区中较多的事故就是厂区爆炸或者火灾，针对这一情况最为紧迫的是找出最优路径，使消防车以最快的速度抵达始发地，避免二次事故的发生，保护生命安全，减少财产损失。对于最优路径的选择方法，Dijkstra算法是当前运用最普遍的。许多学者也都对Dijkstra算法进行了研究与发展，李擎等在经典Dijkstra算法中，针对当前不相连节点间路径长度为无穷大这一特点，首先对两个节点是否相连进行判断，若发现两个节点并不相连时，则舍去相应计算，从而减少计算量。丁浩等研究了如何利用Dijkstra算法来迅速寻找出快递车辆配送派件过程中的最短路径。楚志勇等运用Dijkstra算法解决了乡镇消防站选址的问题。武文越等采用Dijkstra算法快速找出了露天矿运输中的最短运输路径。黄冬梅等通过改进Dijkstra算法，同时采用Matlab进行仿真，可以减少撤离路径的次数，计算出受灾区域到各个安置点的最短路径。 　　以上研究在进行Dijkstra算法的研究时多数是从最短路径这一单一的目的入手，而现实中园区发生爆炸时，道路会受到一定的阻碍，那么在选择路径时考虑的影响因素则需要进行一下改变。文中主要考虑了园区道路疏通的时间，进而求得消防车最优路径。 　　一、传统Dijkstra算法的基本思想 　　（一）Dijkstra算法 　　设G=（V，E，W）是一个带权无向的简单连接图，其中V是G的顶点集合，E是G的边的集合，W是各边上权的集合（Wij≥0）。算法步骤如下： 　　Step1：给起点v1标上P标号P（1）=0，其余顶点标号T1（j）=∞，j=2，3，...，n。该标号表示从起点v1到起点自身的最短路权为0，到其他各个顶点的最短路权上限暂定为∞。 　　Step2：设经过了K-1步标号