最短路問題的應(yīng)用

豆俊梅 孫彩賢

【摘要】社會在進步、科技在發(fā)展，隨之而來的時間的分配、路線的選擇等和最短路問題息息相關(guān)的問題在現(xiàn)在的社會變得越來越突出.最短路問題的本質(zhì)就是在一定的條件下尋找出最有效的方式來達到目的，以使得結(jié)果最佳.最短路問題在理論研究和應(yīng)用上都有著重要的意義.本文首先介紹最短路的算法，而后討論它在實際中的應(yīng)用以及發(fā)展前景.

【關(guān)鍵詞】最短路問題；Dijkstra算法

一、最短路的定義

定義1若圖G=G（V，E）中每一邊e都給有一個實數(shù)W（e），稱為邊e的權(quán)，就把這種圖命名為賦權(quán)圖，記為G=G（V，E，W）.

定義2若圖G=G（V，E）是賦權(quán)圖并且有W（e）≥0，e屬于與E（G），若u到Vi到Vj的路W（u）的權(quán)，則稱W（u）為u的長，長最小的Vi到Vj的路W（u）的路W（u）稱為最短路.

倘若要找出從Vi到Vj的路u，使的全長是最短的，即minWu=∑ei∈uWe.

二、Dijkstra算法

在計算最短路問題時，一種方法是圖論的最基本算法Dijkstra算法，它是用于在最短的計算時間內(nèi)尋找所有節(jié)點最短的路徑，我們通常用來解決兩個點之間最短路徑上的加權(quán)圖的算法，是把時間節(jié)點的Dijkstra算法重復(fù)N次.

Dijkstra算法：

令s=vi，i=1，=v2，v3，…，vn，

并令Wv1=0，Tvj=∞，vj∈.

1對vj∈，求minTvj，Wvi+wij=Tvj.

2求minvj∈sTvj得Tvk，使Tvk=minvi∈sTvj，令Wvk=Tvk.

3若vk=vn則已找到v1到vn的最短路距離Wvk，否則令i=k從中刪去vi轉(zhuǎn)1.

這樣經(jīng)過有限次迭代則可以求出v1到vn的最短路線，

三、最短路問題的應(yīng)用

在平時生活中火災(zāi)是發(fā)生較為頻繁的一種災(zāi)害，其帶來的損失也是巨大的.倘若在火災(zāi)發(fā)生后能夠通過消防的一些措施有效的來控制火勢，毫無疑問時間是最重要的，短暫的時間可以有效的使火災(zāi)所帶來的損失大大減少，火災(zāi)所帶來的經(jīng)濟損失常常是不可預(yù)測的，這與火災(zāi)的持續(xù)時間、燃燒面積、火災(zāi)場地等因素都有著必不可分的聯(lián)系.對于我們平時生活中常發(fā)生火災(zāi)的位置和火災(zāi)所帶來損失的數(shù)據(jù)統(tǒng)計可以知道主要與火災(zāi)的持續(xù)時間有關(guān).這就對消防隊的到達時間有著很重要的關(guān)系，只有及時到達火災(zāi)現(xiàn)場并作出相應(yīng)的措施才能降低火災(zāi)做帶來的損失.基于我國的通訊、道路和消防設(shè)備的實際情況以及對大量的火災(zāi)案例分析可以得出只有在15分鐘內(nèi)到達火災(zāi)現(xiàn)場作出滅火措施才能有效的防止火勢蔓延并可以有效的撲滅火災(zāi).但是由于在實際的消防資源調(diào)度等方面的各種不及時，常常使得消防人員不能及時到達火災(zāi)現(xiàn)場，以致丟失了好的救災(zāi)時機，而我們運用地理信息中的Dijkstra最短路徑的算法就可以解決如何快速調(diào)動消防救援到達火災(zāi)現(xiàn)場的問題.

運用Dijkstra最短路徑的算法中，可以通過計算路徑的邊權(quán)來衡量最短路徑，算法參數(shù)標(biāo)準(zhǔn)建立的重要因素是確定邊權(quán)以使得所設(shè)定的邊權(quán)更符合系統(tǒng)的需要，邊權(quán)值設(shè)定的好壞直接決定了算法的適用性.在現(xiàn)在的交通網(wǎng)絡(luò)中路線最短不一定就是耗時最短的路徑，基于此如何選擇合適的權(quán)值是設(shè)計最優(yōu)路線的重要前提.交通，天氣，車道數(shù)，道路狀況等都是影響消防車到火災(zāi)現(xiàn)場的重要因素.我們把最優(yōu)目標(biāo)設(shè)定為救援時間最短，這樣我們就可以研究道路的權(quán)重.一般而言，可以采用下面的方案來確定出行時間度量的道路權(quán)重.方案：用行程時間和阻力功能和延遲模型相交的運動模式來進行計算當(dāng)時時間段的路段行程時間和交叉口延誤，以此來確定權(quán)重.于是我們就可以很好的把交通流考慮了進去，很好的把實時的特點表現(xiàn)出來，這個方案可以很好的解決實際情況并且技術(shù)上也完全沒有問題，綜合考慮了實用性與可行性.

因此，把路徑權(quán)值的最優(yōu)指標(biāo)設(shè)定為所選取的時間，并用路阻函數(shù)求出道路交通網(wǎng)中的各路段權(quán)值，在此基礎(chǔ)上利用Dijkstra最短路徑算法實現(xiàn)消防力量掉級的最優(yōu)化.

四、小結(jié)

最短路問題是現(xiàn)代運籌學(xué)的重要組成部分，也是經(jīng)濟學(xué)所研究的重要課題之一，最短路問題及應(yīng)用的重要性越來越多的被人們所認識.隨著科學(xué)技術(shù)的和生產(chǎn)的發(fā)展，最短路定義的內(nèi)涵也在不斷地豐富、外延不斷延伸.最短路問題的應(yīng)用在現(xiàn)實生活中的日益廣泛，在社會生產(chǎn)和實踐中發(fā)揮著越來越重要的作用.最短路問題的研究理論和方法的發(fā)展源于實踐也服務(wù)于實踐.最短路問題的要求，合理設(shè)定約束條件，通過數(shù)學(xué)上的分析運算得出各種求得最短路的方案，最后結(jié)合實際提出綜合性的合理安排，達到最好的效果.最短路問題在數(shù)據(jù)結(jié)構(gòu)這門課程中有涉及.在最求高效率的社會生活中最短路問題及應(yīng)用也是一個較大的研究領(lǐng)域，一個最具潛力的領(lǐng)域.

所以最短路問題及它的應(yīng)用的研究對于我們現(xiàn)在的生活有著很大的影響，在這樣一個最求高效率的社會生活中，我們還要堅持不懈的進行研究，來造福全人類.

【參考文獻】

[1]卜月華.圖論及其應(yīng)用[M].南京：東南大學(xué)出版社，2000.

[2]余為波，王濤.基于圖論的艦船通道路線優(yōu)化[J].2008.

[3]李玲.最短路問題在運輸網(wǎng)絡(luò)中的應(yīng)用[J].2006.

[4]戴文舟.交通網(wǎng)絡(luò)中最短路徑算法的研究[D].重慶大學(xué)碩士學(xué)位論文，2004.

[5]謝灼利，等.地鐵車站站臺火災(zāi)中人員的安全疏散[J].中國安全科學(xué)學(xué)報，2004，14（7）：21.

[6]榮瑋.基于道路網(wǎng)的最短路徑算法的研究與實現(xiàn)[D].武漢理工大學(xué)碩士學(xué)位論文，2005.