淺析Ｄｉｊｋｓｔｒａ最短路徑算法在消防力量調集中的應用

劉　蕊　李　峰

摘要：文章從我國的火災形勢出發(fā)，以優(yōu)化城市道路交通網中路段的權值為出發(fā)點，結合消防工作實際情況的特點，介紹了消防力量調集路徑最優(yōu)指標的選取方案，著重分析了Dijkstra最短路徑算法的基本原理，并給出了算法優(yōu)化方案。優(yōu)化后的算法能夠有效降低Dijkstra算法的時間復雜性，提高運行效率。實例應用表明，該方法兼具靈活性和實用性，能夠滿足消防滅火救援工作中實現(xiàn)消防力量優(yōu)化調集的要求。

關鍵字：Dijkstra算法；最短路徑；力量調集

中圖分類號：TP311.1文獻標識碼：A文章編號：1009-2374（2009）02-00734-02

火災是城市中較為頻繁的災害，其損失經常是巨大的。如果在火災發(fā)生后的短暫時間內，消防力量能有效地控制火勢，則火災損失會大大減少?；馂牡慕洕鷵p失有很大的波動性，它與火災的持續(xù)時間、燃燒物的類別、過火面積等因素有關。但是，對于一個具體的建筑物子系統(tǒng)，火災損失的變化主要與火災持續(xù)時間有關。消防隊必須在15分鐘內達到火場出水，這是基于我國通訊、道路和消防裝備的實際情況以及對大量的火災案例的分析得出的，這樣才能有效地撲救火災并防止火勢繼續(xù)蔓延。但在實際工作中往往由于消防資源調度不當?shù)雀鞣N遲滯因素使得消防人員不能盡早趕到火災事故現(xiàn)場，喪失了對早期火災撲救的良好時機。為將損失降低到最低程度，消防部門面臨的問題是如何迅速調動消防救援力量到達事故地點及時撲滅火災，這就涉及到調集路徑選取的問題。地理信息系統(tǒng)中的DIJKSTRA最短路徑算法可以很好的解決這個問題。

一、消防力量調集路徑最優(yōu)指標的選取

Dijkstra算法在通用路徑選擇算法中，對最短路徑的衡量標準是通過計算路徑的邊權來決定的。如何確定邊權，使設定的邊權更符合系統(tǒng)實際的需要，是建立算法參數(shù)標準的重要因素，其值設定的好壞，直接決定了算法的適用性。在實際城市交通網絡中，道路長度最短的路徑不一定是耗時最短的。如何設定最優(yōu)路徑的標準也是設計權值的重要前提。影響消防車輛到達火災事故現(xiàn)場時間的因素很多，如車流量、車道數(shù)、時間段、路面狀況等等。將救援時間最短作為最優(yōu)目標，相應的道路權重如何標定是一個非常值得研究的問題。一般而言，確定以出行時間度量的道路權重建議采用以下方案：

引進表征路段行程時間與交通流量之間關系的路阻函數(shù)模型以及交叉口延誤模型，計算當前時段的路段行程時間及交叉口延誤，以此確定道路權重。這樣既考慮了交通流的特性，體現(xiàn)了實時因素，又在當前基礎設施狀況允許的范圍內。該方案較好地反映了現(xiàn)實情況，且技術上切實可行，綜合考慮了實用性與可行性。

因此，本文選取時間作為路徑權值的最優(yōu)指標，并用路阻函數(shù)求出道路交通網中各路段的權值，在此基礎上利用DIJKSTRA最短路徑算法實現(xiàn)消防力量調集的最優(yōu)化。

二、Dijkstra最短路徑經典算法及分析

（一）問題定義

我們討論的問題是城市消防單源點的最短路徑，即對于給定帶時間權的無向圖G、源點Vi和終點Vj，求得源Vi和終點Vj之間路徑中的最短路徑。

（二）Dijkstra 算法

我們設定一個輔助向量D[i]。D[i]表示當前從源點V到每個終點Vi的最短路徑的時間長度。它的初始值為：如果V到Vi有直接相聯(lián)的路徑，則D[i]為這條路徑的時間權值。否則，設定D[i]=∞，設D[j]=min{ D[i]|Vi∈V }。顯然，D[j]為從V出發(fā)的一條最短路徑。下一條次短路徑的長度一定是：D[j] = min{ D[i]|Vi∈V-S }，其中S為已求得最短路徑的終點的集合。根據(jù)對以上求出的最短時間路徑序列的查詢，我們可得出兩地的最短時間路徑。

（三）Dijkstra算法優(yōu)化及分析

1．優(yōu)化Dijkstra算法的思路

根據(jù)以上對Dijkstra算法的分析，我們可以知道，當n較大時，Dijkstra算法的運行時間急劇增加。如果能有效地減小n值，就能大大地減少運行時間，提高效率?；谝陨峡紤]，為了有效地減小n值，我們把需要計算兩節(jié)點最佳時間路徑的公路網圖分成若干個子圖，對每個子圖分別采用Dijkstra算法進行計算，再把每段計算的節(jié)點連接起來，就是我們需要的結果。在把一個圖劃分成若干個子時遵循以下原則：

（1）根據(jù)幾何中關于兩點間的時間距離最短的原理，我們用直線連接源點和終點，最佳路徑一般情況應在這條直線附近。劃分子圖應順著這條直線來進行。

（2）每個子圖應盡可能均勻，即每個子圖的節(jié)點數(shù)基本上接近。否則，本優(yōu)化算法效果不明顯。如果在劃分子圖時，每個子圖的節(jié)點數(shù)相差懸殊，則子圖查找效率低，造成優(yōu)化算法效果不明顯。

（3）劃分子圖盡可能使圖的邊接近連接源點和終點這條直線附近，以減少重復計算的次數(shù)，提高命中率。

2．優(yōu)化Dijkstra算法的描述

（1）依據(jù)以上原則，把一個公路網圖劃分成若干個子圖。

（2）劃分時，每個子圖的節(jié)點最接近連接源點和終點的直線。

（3）分別對每個子圖采用Dijkstra算法進行計算。

（4）我們把相鄰子圖的源點和終點分別進行核對。如果前一子圖的終點就是后一子圖的源點，那么我們連接這兩段，并且認為這段就是最佳路徑中的一段；如果前一子圖的終點不是后一子圖的源點，那么我們修改前一子圖的終點，把它定義成后一子圖的源點，再對前一子圖采用Dijkstra算法進行計算，同時，修改后一子圖的源點，把它定義成前一子圖的終點，再對后一子圖采用Dijkstra算法進行計算，連接這兩段。根據(jù)計算結果，取這兩段中權值最小的一段，作為最佳路徑中的一段。

（5）重復以上步驟，直到找出連接源點和終點的最佳路徑。

采用以上方法找出的路徑不一定是最短路徑，但它是最接近或就是最短路徑。

三、結語

通過對消防力量調集最短路徑算法的研究，了解Dijkstra基本算法和優(yōu)化算法。同時，我們也注意到，優(yōu)化Dijkstra算法適應等級較高的公路，對于等級較低的公路，若公路線型過于彎曲，可能效果不理想。

參考文獻

[1]黃偉東，萬義玲．公路網最佳路徑算法的研究[J]．南昌大學學報（工科版），2003，（3）．

[2]魏新宇．消防滅火救援最優(yōu)路徑算法研究[D]．西安科技大學，2006，（4）．

[3]李斌．基于GIS的城市消防信息系統(tǒng)[D]．貴州大學，2006，（5）．