豆俊梅 孫彩賢

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

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

一、最短路的定義

定義1若圖G=G（V，E）中每一邊e都給有一個(gè)實(shí)數(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的長(zhǎng)，長(zhǎng)最小的Vi到Vj的路W（u）的路W（u）稱為最短路.

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

二、Dijkstra算法

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

Dijkstra算法：

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

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

1對(duì)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)用

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

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

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

四、小結(jié)

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

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

【參考文獻(xiàn)】

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

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

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

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

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

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