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

《dijkstra算法在园区消防车最优路径中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Dijkstra算法在园区消防车最优路径中的应用摘要：本文针对当前园区消防车辆到达受灾点的事故蔓延状况随到达时间的延长而加重的问题，研究并提出了改进的Dijkstra算法。并且通过对传统Dijkstra算法与改进的Dijkstra算法进行比较，得出改进的Dijkstra算法求得的最优路径使消防车到达的时间更短。关键词：园区事故Dijkstra算法改进的Dijkstra:fjI.中图分类号：U491.2文献标识码：ATheimprovedDijkstraalgorithmapplicationinoptimalpathselect

2、ionofthecampusfiretruckZHANGTaol，LiDe-tang2,ZhengKai-jul(1.Portsandtransportationengineeringcollege，ZhejiangOceanUniversity;2.SchoolofNavalArchitectureandMechanical-electricalEngineering，ZhejiangOceanUniversity、OffshoreinZhejiangprovincekeylaboratoryofoceanengineerin

3、gtechnologyZhoushan316000，China)Abstract：Inallusiontotheproblemofthecurrentcampusfirevehiclesarrivedatthepointofaccidentalongwiththeextensionoftimeofarrivalisaggravating，theresearchandtheimprovedDijkstraalgorithmareputforward.BycomparingtraditionalDijkstraalgorithman

4、dtheimprovedDijkstraalgorithm，itisconcludedthattheimprovedDijkstraalgorithmobtainstheoptimalpathtakinglesstimetomakethefireenginesarrived.KeyWords:TheaccidentofindustrialparkDijkstraalgorithmTheimprovedDijkstraalgorithm由于全球经济的不断快速发展，园区经济最为促进经济快速增长的重要产业也在发生着巨大的变化。在园区发

5、展过程中难免存在一定的危险源，当危险源在一定环境下会发生事故，在园区中较多的事故就是厂区爆炸或者火灾，针对这一情况最为紧迫的是找出最优路径，使消防车以最快的速度抵达始发地，避免二次事故的发生，保护生命安全，减少财产损失。对于最优路径的选择方法，Dijkstra算法是当前运用最普遍的。许多学者也都对Dijkstra算法进行了研宄与发展，李擎等在经典Dijkstra算法中，针对当前不相连节点间路径长度为无穷大这一特点，首先对两个节点是否相连进行判断，若发现两个节点并不相连时，则舍去相应计算，从而减少计算量。丁浩等研宄了如何利用Dij

6、kstra算法来迅速寻找出快递车辆配送派件过程中的最短路径。楚志勇等运用Dijkstra算法解决了乡镇消防站选址的问题。武文越等采用Dijkstra算法快速找出了露天矿运输中的最短运输路径。黄冬梅等通过改进Dijkstra算法，同时采用Matlab进行仿真，可以减少撤离路径的次数，计算出受灾区域到各个安置点的最短路径。以上研宄在进行Dijkstra算法的研宄时多数是从最短路径这一单一的目的入手，而现实中园区发生爆炸时，道路会受到一定的阻碍，那么在选择路径时考虑的影响因素则需要进行一下改变。文中主要考虑了园区道路疏通的时间，进而求

7、得消防车最优路径。一、传统Dijkstra算法的基本思想（一）Dijkstra算法设G=（V,E，W）是一个带权无向的简单连接图，其中V是G的顶点集合，E是G的边的集合，W是各边上权的集合（WijX））。算法步骤如下：Step1:给起点vl标上P标号P（1）=0，其余顶点标号T1（j）=°°，j=2，3，…，n。该标号表示从起点vl到起点自身的最短路权为0,到其他各个顶点的最短路权上限暂定为…。Step2：设经过了K-l步标号计算，顶点vi是刚得到P标号的点，则对所有没有得到P标号的点进行下一步新的标号，即第k步计算；考虑到所有

8、与顶点vi相邻且没有标上P标号的点vj集合，分别修改其对应的T标号：Tk(j)=min｛T(j),P(i)+dij｝；在所有的T标号中，选出最小的T标号Tk(jO)：Tk(jO)=min｛Tk(j)，T(r)｝。Step3:给顶点jO标上P标号：P(jO)二Tk