最短路問題及其應用參考模板

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、0;the 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 =&

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

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

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

20、;v;        / 找出當前未使用的點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、#160;&& cuj<maxint)                                    int newdist = distu + cu

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

26、160;                   distj = newdist;                        prevj =

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

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

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

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

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

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

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

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

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

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