最短路問(wèn)題及其應(yīng)用參考模板

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

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

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

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

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

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

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

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

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

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

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

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

13、160;int maxnum = 100;const int maxint = 999999; / 各數(shù)組都從下標(biāo)1開(kāi)始/int distmaxnum;     / 表示當(dāng)前點(diǎn)到源點(diǎn)的最短路徑長(zhǎng)度/int prevmaxnum;     / 記錄當(dāng)前點(diǎn)的前一個(gè)結(jié)點(diǎn)/int cmaxnummaxnum;   / 記錄圖的

14、兩點(diǎn)間路徑長(zhǎng)度/int n, line;             / 圖的結(jié)點(diǎn)數(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;    / 判斷是否已存入該點(diǎn)到S集合中    for(int i=1; i<=n; +i)            disti = cvi;        si =&

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

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

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

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

21、60;                        u = j;              / u保存當(dāng)前鄰接點(diǎn)中距離最小的點(diǎn)的號(hào)碼    

22、0;           tmp = distj;                        su = 1;    / 表示u點(diǎn)已存入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;                                         / 查找從源點(diǎn)v到終點(diǎn)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;     / 表示當(dāng)前點(diǎn)到源點(diǎn)的最短路徑長(zhǎng)度   &#

32、160;int prevmaxnum;     / 記錄當(dāng)前點(diǎn)的前一個(gè)結(jié)點(diǎn)    int cmaxnummaxnum;   / 記錄圖的兩點(diǎn)間路徑長(zhǎng)度    int n, line;             / 圖的結(jié)點(diǎn)數(shù)和路徑數(shù) 

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

34、e;    int p, q, len;          / 輸入p, q兩點(diǎn)及其路徑長(zhǎng)度     / 初始化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;  &