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

1、最短路問題及其應(yīng)用顧碧芬 06200103摘要：主要介紹最短路的兩種算法，迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。以及這兩種算法在實際問題中的應(yīng)用和比較。1 引言最短路問題是圖論理論的一個經(jīng)典問題。尋找最短路徑就是在指定網(wǎng)絡(luò)中兩結(jié)點間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時間、費用、線路容量等。最短路徑算法的選擇與實現(xiàn)是通道路線設(shè)計的基礎(chǔ),最短路徑算法是計算機科學與地理信息科學等領(lǐng)域的研究熱點,很多網(wǎng)絡(luò)相關(guān)問題均可納入最短路徑問題的范疇之中。經(jīng)典的圖論與不斷發(fā)展完善的計算機數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。

2、2 最短路2.1 最短路的定義對最短路問題的研究早在上個世紀60年代以前就卓有成效了,其中對賦權(quán)圖的有效算法是由荷蘭著名計算機專家E.W.Dijkstra在1959年首次提出的,該算法能夠解決兩指定點間的最短路,也可以求解圖G中一特定點到其它各頂點的最短路。后來海斯在Dijkstra算法的基礎(chǔ)之上提出了海斯算法。但這兩種算法都不能解決含有負權(quán)的圖的最短路問題。因此由Ford提出了Ford算法,它能有效地解決含有負權(quán)的最短路問題。但在現(xiàn)實生活中,我們所遇到的問題大都不含負權(quán),所以我們在的情況下選擇Dijkstra算法。定義1若圖G=G(V,E)中各邊e都賦有一個實數(shù)W(e),稱為邊e的權(quán),則稱這

3、種圖為賦權(quán)圖,記為G=G(V,E,W)。定義2若圖G=G(V,E)是賦權(quán)圖且,若u是到的路的權(quán),則稱為的長,長最小的到的路稱為最短路。若要找出從到的通路,使全長最短,即。2.2 最短路問題算法的基本思想及基本步驟在求解網(wǎng)絡(luò)圖上節(jié)點間最短路徑的方法中,目前國內(nèi)外一致公認的較好算法有迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。這兩種算法中,網(wǎng)絡(luò)被抽象為一個圖論中定義的有向或無向圖,并利用圖的節(jié)點鄰接矩陣記錄點間的關(guān)聯(lián)信息。在進行圖的遍歷以搜索最短路徑時,以該矩陣為基礎(chǔ)不斷進行目標值的最小性判別,直到獲得最后的優(yōu)化路徑。Dijkstra算法是圖論中確定最短路的基本方法,也是其它算法的

4、基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點之間的最短路徑,通常采用兩種方法。一種方法是每次以一個結(jié)點為源點,重復(fù)執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法,其時間復(fù)雜度為,雖然與重復(fù)執(zhí)行Dijkstra算法n次的時間復(fù)雜度相同,但其形式上略為簡單,且實際運算效果要好于前者。Dijkstra算法基本步驟：令：并令：1、 對，求。2、 求得，使=令3、若則已找到到的最短路距離，否則令從中刪去轉(zhuǎn)1這樣經(jīng)過有限次迭代則可以求出到的最短路線，可以用一個流程圖來表示：第一步 先取意即到的距離為0,而是對所賦的初值。第二步 利用已知,根據(jù)對進行修正。第三步 對所有修正后的求

5、出其最小者。其對應(yīng)的點是所能一步到達的點中最近的一個,由于所有。因此任何從其它點中轉(zhuǎn)而到達的通路上的距離都大于直接到的距離,因此就是到的最短距離,所以在算法中令并從s中刪去,若k=n則就是到的最短路線,計算結(jié)束。否則令回到第二步,繼續(xù)運算,直到k=n為止。這樣每一次迭代,得到到一點的最短距離,重復(fù)上述過程直到。Floyd算法的基本原理和實現(xiàn)方法為:如果一個矩陣其中表示與間的距離,若與間無路可通,則為無窮大。與間的最短距離存在經(jīng)過與間的和不經(jīng)過兩種情況,所以可以令,n(n為節(jié)點數(shù))。檢查與的值,在此,與分別為目前所知的到與到的最短距離,因此,就是到經(jīng)過的最短距離。所以,若有,就表示從出發(fā)經(jīng)再到的

6、距離要比原來的到距離短,自然把到的重寫成。每當一個搜索完,就是目前到的最短距離。重復(fù)這一過程,最后當查完所有時,就為到的最短距離。3 最短路的應(yīng)用3.1在運輸網(wǎng)絡(luò)中的應(yīng)用設(shè)6個城市之間的一個公路網(wǎng)(圖1)每條公路為圖中的邊,邊上的權(quán)數(shù)表示該段公路的長度(單位:百公里),設(shè)你處在城市,那么從到應(yīng)選擇哪一路徑使你的費用最省。解:首先設(shè)每百公里所用費用相同,求到的費用最少,既求到的最短路線。為了方便計算,先作出該網(wǎng)絡(luò)的距離矩陣,如下:(0)設(shè),(1)第一次迭代計算如下取,令由于,令轉(zhuǎn)(1)第二次迭代:算如下取令由于,令轉(zhuǎn)(1)第三次迭代:算如下取由于,令轉(zhuǎn)(1)第四次迭代:算如下取由于,令轉(zhuǎn)(1)第

7、五次迭代:算如下由于。因此已找到到的最短距離為12。計算結(jié)束。找最短路線:逆向追蹤得最短距離為12,即從城市到城市的距離最短,即費用最省。3.2在艦船通道路線設(shè)計中的應(yīng)用利用圖論的經(jīng)典理論和人群流量理論研究艦船人員通道路線的優(yōu)化設(shè)計及最優(yōu)線路選擇。首先介紹圖論相關(guān)理論,對船舶通道進行路網(wǎng)抽象,建立網(wǎng)絡(luò)圖,然后根據(jù)人群流動的相關(guān)理論,選取不同擁擠情況下的人員移動速度,從而確定各條路段(包括樓梯)的行程時間。以行程時間作為通道網(wǎng)絡(luò)的路權(quán)，得出路阻矩陣以選擇一對起點/終點的最短時間路線為目標,建立最短路徑問題的數(shù)學模型,利用經(jīng)典的Floyd算法確定最短路徑。將此方法應(yīng)用于某艦艇多層甲板的通道網(wǎng)絡(luò)中,

8、計算結(jié)果并進行討論,最后在此研究的基礎(chǔ)上對通道設(shè)計相關(guān)問題的深化和拓展進行了探討和總結(jié),并提出設(shè)想。路線優(yōu)化技術(shù)通常采用圖論中的“圖”來表示路網(wǎng),船舶通道路網(wǎng)與圖論的路網(wǎng)對應(yīng)關(guān)系為:結(jié)點通道的交叉口或斷頭路的終點;邊兩結(jié)點之間的路段稱為邊,若規(guī)定了路段的方向,則稱為弧;邊(弧)的權(quán)路段某個或某些特征屬性的量化表示。路權(quán)的標定決定了最短的路徑搜索依據(jù),也就是搜索指標。根據(jù)不同的最優(yōu)目標,可以選擇不同的路段屬性。由于艦船上除了平面上的通道之外還有垂直方向的樓梯(或直梯),如果以最短路程距離作為優(yōu)化目標,路線的效率未必最高(距離最短未必耗時最少)。所以,以最短行程時間作為優(yōu)化的目標,道路權(quán)重即為各路

9、段的平均行程時間。對于要研究的對象,取各條通道的起點(或終點)和交叉點為圖的頂點,各路段為邊,路權(quán)為路段行走的平均時間。尋找從起點到終點的最短時間路徑即為最優(yōu)路徑。在規(guī)定了結(jié)點、邊和權(quán)值以后,便將路網(wǎng)抽象為一個賦權(quán)無向圖或賦權(quán)有向圖,從而確定路網(wǎng)中某兩地間的最優(yōu)路線便轉(zhuǎn)化為圖論中的最短路徑問題。首先將空間問題抽象為圖,圖2為某艦的兩層甲板的部分抽象圖,上下兩個平面上縱橫交錯的直線為各層甲板的主要通道,連接兩層甲板的直線表示樓梯,包括2個直梯和3個斜梯。每條路段上的標注中,表示路段實際長度或者樓梯的類型,m;b表示此路段的行程時間(即路權(quán)),s如(40,32)。圖2 兩層甲板的部分抽象圖圖3 賦

10、權(quán)圖再利用上述求最短的方法即可求得需要的通道路線。4 結(jié)語本文將最短路理論應(yīng)用到實際生活中，尤其是在艦船通道路線中的應(yīng)用具有很重要的意義。將實際生活中出現(xiàn)的安全隱患盡量降低。同時也凸顯出學習和應(yīng)用最短路問題原理的重要性。另外，最短路問題在城市道路建設(shè)、物資供應(yīng)站選址等問題上也有很重要的作用。分析和研究最短路問題趨于熱門化。注：殷劍宏 ,吳開亞.圖論及其算法M. 中國科學技術(shù)出版社 秦裕瑗 ,秦明復(fù).運籌學簡明教材M. 高等教育出版社 卜月華 圖論及其應(yīng)用 最短路問題在運輸網(wǎng)絡(luò)中的應(yīng)用 基于圖論的艦船通道路線優(yōu)化參考文獻：【1】 卜月華 圖論及其應(yīng)用 南京：東南大學出版社，2000【2】 基于圖

11、論的艦船通道路線優(yōu)化 余為波 王濤 2008【3】 最短路問題在運輸網(wǎng)絡(luò)中的應(yīng)用 李玲 2006【4】 戴文舟. 交通網(wǎng)絡(luò)中最短路徑算法的研究 D . 重慶大學碩士學位論文 ,2004.【5】 謝灼利,等.地鐵車站站臺火災(zāi)中人員的安全疏散J.中國安全科學學報 ,2004,14(7):21.【6】 榮瑋.基于道路網(wǎng)的最短路徑算法的研究與實現(xiàn).武漢理工大學碩士學位論文D,2005.【7】 朱建青 ,張國梁.數(shù)學建模方法M. 鄭州大學出版社.【8】 楊民助 ,運籌學M. 西安交通大學出版社.【9】 殷劍宏 ,吳開亞.圖論及其算法M. 中國科學技術(shù)出版社.【10】 王朝瑞.圖論M. 國防工業(yè)出版社.【

12、11】 姚思瑜.數(shù)學規(guī)劃與組合優(yōu)化M. 浙江大學出版社.【12】 秦裕瑗 ,秦明復(fù).運籌學簡明教材M. 高等教育出版社./* About:    有向圖的Dijkstra算法實現(xiàn)* Author:   Tanky Woo* Blog:     www.WuTianQ*/ #include <iostream>using namespace std; const in

13、t maxnum = 100;const int maxint = 999999; / 各數(shù)組都從下標1開始/int distmaxnum;     / 表示當前點到源點的最短路徑長度/int prevmaxnum;     / 記錄當前點的前一個結(jié)點/int cmaxnummaxnum;   / 記錄圖的兩點間路徑長

14、度/int n, line;             / 圖的結(jié)點數(shù)和路徑數(shù) / n - n nodes/ v - the source node/ dist - the distance from the ith node to the&

15、#160;source node/ prev - the previous node of the ith node/ c - every two nodes' distancevoid Dijkstra(int n, int v, int *dist, int *prev, int cmaxnummaxnum) 

16、60;  bool smaxnum;    / 判斷是否已存入該點到S集合中    for(int i=1; i<=n; +i)            disti = cvi;        si = 0

17、;     / 初始都未用過該點        if(disti = maxint)            previ = 0;        else     

18、0;      previ = v;        distv = 0;    sv = 1;     / 依次將未放入S集合的結(jié)點中，取dist最小值的結(jié)點，放入結(jié)合S中    / 一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間

19、的最短路徑長度    / 注意是從第二個節(jié)點開始，第一個為源點    for(int i=2; i<=n; +i)            int tmp = maxint;        int u = v;

20、60;       / 找出當前未使用的點j的distj最小值        for(int j=1; j<=n; +j)            if(!sj) && distj<tmp)    

21、60;                       u = j;              / u保存當前鄰接點中距離最小的點的號碼     

22、0;          tmp = distj;                        su = 1;    / 表示u點已存入S集合中  &

23、#160;          / 更新dist            for(int j=1; j<=n; +j)                if(!sj) &

24、amp;& cuj<maxint)                                    int newdist = distu + cuj;

25、0;                   if(newdist < distj)                         &#

26、160;                  distj = newdist;                        prevj = 

27、u;                                         / 查找從源點v到終點u的路徑，并輸出void searchPath(int

28、0;*prev,int v, int u)    int quemaxnum;    int tot = 1;    quetot = u;    tot+;    int tmp = prevu;    while(tmp !=

29、 v)            quetot = tmp;        tot+;        tmp = prevtmp;        quetot = v;

30、60;   for(int i=tot; i>=1; -i)        if(i != 1)            cout << quei << " -> "   &#

31、160;    else            cout << quei << endl; int main()    int distmaxnum;     / 表示當前點到源點的最短路徑長度    in

32、t prevmaxnum;     / 記錄當前點的前一個結(jié)點    int cmaxnummaxnum;   / 記錄圖的兩點間路徑長度    int n, line;             / 圖的結(jié)點數(shù)和路徑數(shù)  

33、;  freopen("input.txt", "r", stdin);    / 各數(shù)組都從下標1開始     / 輸入結(jié)點數(shù)    cin >> n;    / 輸入路徑數(shù)    cin >> line;

34、0;   int p, q, len;          / 輸入p, q兩點及其路徑長度     / 初始化c為maxint    for(int i=1; i<=n; +i)        for(i

35、nt j=1; j<=n; +j)            cij = maxint;     for(int i=1; i<=line; +i)              cin >

36、> p >> q >> len;        if(len < cpq)       / 有重邊                    cpq = len;  &#