dijkstra算法在園區(qū)消防車最優(yōu)路徑中的應(yīng)用

《dijkstra算法在園區(qū)消防車最優(yōu)路徑中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、Dijkstra算法在園區(qū)消防車最優(yōu)路徑中的應(yīng)用摘要：本文針對(duì)當(dāng)前園區(qū)消防車輛到達(dá)受災(zāi)點(diǎn)的事故蔓延狀況隨到達(dá)時(shí)間的延長(zhǎng)而加重的問(wèn)題，研究并提出了改進(jìn)的Dijkstra算法。并且通過(guò)對(duì)傳統(tǒng)Dijkstra算法與改進(jìn)的Dijkstra算法進(jìn)行比較，得出改進(jìn)的Dijkstra算法求得的最優(yōu)路徑使消防車到達(dá)的時(shí)間更短。關(guān)鍵詞：園區(qū)事故Dijkstra算法改進(jìn)的Dijkstra:fjI.中圖分類號(hào)：U491.2文獻(xiàn)標(biāo)識(shí)碼：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由于全球經(jīng)濟(jì)的不斷快速發(fā)展，園區(qū)經(jīng)濟(jì)最為促進(jìn)經(jīng)濟(jì)快速增長(zhǎng)的重要產(chǎn)業(yè)也在發(fā)生著巨大的變化。在園區(qū)發(fā)

5、展過(guò)程中難免存在一定的危險(xiǎn)源，當(dāng)危險(xiǎn)源在一定環(huán)境下會(huì)發(fā)生事故，在園區(qū)中較多的事故就是廠區(qū)爆炸或者火災(zāi)，針對(duì)這一情況最為緊迫的是找出最優(yōu)路徑，使消防車以最快的速度抵達(dá)始發(fā)地，避免二次事故的發(fā)生，保護(hù)生命安全，減少財(cái)產(chǎn)損失。對(duì)于最優(yōu)路徑的選擇方法，Dijkstra算法是當(dāng)前運(yùn)用最普遍的。許多學(xué)者也都對(duì)Dijkstra算法進(jìn)行了研宄與發(fā)展，李擎等在經(jīng)典Dijkstra算法中，針對(duì)當(dāng)前不相連節(jié)點(diǎn)間路徑長(zhǎng)度為無(wú)窮大這一特點(diǎn)，首先對(duì)兩個(gè)節(jié)點(diǎn)是否相連進(jìn)行判斷，若發(fā)現(xiàn)兩個(gè)節(jié)點(diǎn)并不相連時(shí)，則舍去相應(yīng)計(jì)算，從而減少計(jì)算量。丁浩等研宄了如何利用Dij

6、kstra算法來(lái)迅速尋找出快遞車輛配送派件過(guò)程中的最短路徑。楚志勇等運(yùn)用Dijkstra算法解決了鄉(xiāng)鎮(zhèn)消防站選址的問(wèn)題。武文越等采用Dijkstra算法快速找出了露天礦運(yùn)輸中的最短運(yùn)輸路徑。黃冬梅等通過(guò)改進(jìn)Dijkstra算法，同時(shí)采用Matlab進(jìn)行仿真，可以減少撤離路徑的次數(shù)，計(jì)算出受災(zāi)區(qū)域到各個(gè)安置點(diǎn)的最短路徑。以上研宄在進(jìn)行Dijkstra算法的研宄時(shí)多數(shù)是從最短路徑這一單一的目的入手，而現(xiàn)實(shí)中園區(qū)發(fā)生爆炸時(shí)，道路會(huì)受到一定的阻礙，那么在選擇路徑時(shí)考慮的影響因素則需要進(jìn)行一下改變。文中主要考慮了園區(qū)道路疏通的時(shí)間，進(jìn)而求

7、得消防車最優(yōu)路徑。一、傳統(tǒng)Dijkstra算法的基本思想（一）Dijkstra算法設(shè)G=（V,E，W）是一個(gè)帶權(quán)無(wú)向的簡(jiǎn)單連接圖，其中V是G的頂點(diǎn)集合，E是G的邊的集合，W是各邊上權(quán)的集合（WijX））。算法步驟如下：Step1:給起點(diǎn)vl標(biāo)上P標(biāo)號(hào)P（1）=0，其余頂點(diǎn)標(biāo)號(hào)T1（j）=°°，j=2，3，…，n。該標(biāo)號(hào)表示從起點(diǎn)vl到起點(diǎn)自身的最短路權(quán)為0,到其他各個(gè)頂點(diǎn)的最短路權(quán)上限暫定為…。Step2：設(shè)經(jīng)過(guò)了K-l步標(biāo)號(hào)計(jì)算，頂點(diǎn)vi是剛得到P標(biāo)號(hào)的點(diǎn)，則對(duì)所有沒(méi)有得到P標(biāo)號(hào)的點(diǎn)進(jìn)行下一步新的標(biāo)號(hào)，即第k步計(jì)算；考慮到所有

8、與頂點(diǎn)vi相鄰且沒(méi)有標(biāo)上P標(biāo)號(hào)的點(diǎn)vj集合，分別修改其對(duì)應(yīng)的T標(biāo)號(hào)：Tk(j)=min｛T(j),P(i)+dij｝；在所有的T標(biāo)號(hào)中，選出最小的T標(biāo)號(hào)Tk(jO)：Tk(jO)=min｛Tk(j)，T(r)｝。Step3:給頂點(diǎn)jO標(biāo)上P標(biāo)號(hào)：P(jO)二Tk