《圖的最短路徑算法介紹與應(yīng)用（論文）5600字》

引言最短路徑問(wèn)題一直是計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科的一個(gè)研究熱點(diǎn)。國(guó)內(nèi)外大量專家學(xué)者對(duì)此問(wèn)題進(jìn)行了深入研究。經(jīng)典的圖論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷出現(xiàn)。它們?cè)诳臻g復(fù)雜度、時(shí)間復(fù)雜度、易實(shí)現(xiàn)性及應(yīng)用范圍各有特色。最短路徑在當(dāng)今社會(huì)中顯得越來(lái)越重要。它不僅節(jié)省了大量的時(shí)間，降低了配送成本，方便了人們的生產(chǎn)和生活還提高了服務(wù)質(zhì)量，增加了公司的經(jīng)濟(jì)效益，從而提高了產(chǎn)品的競(jìng)爭(zhēng)力，為現(xiàn)代化的發(fā)展打下了良好的基礎(chǔ)。由于最短路徑問(wèn)題的廣泛應(yīng)用，很多學(xué)者都對(duì)此進(jìn)行了深入的研究，隨著研究成果的也是產(chǎn)生了一些經(jīng)典的算法。近年來(lái)，對(duì)最短路徑研究的熱度依然不減，并且時(shí)間復(fù)雜度也降得越來(lái)越低。從實(shí)際意義上講，沒(méi)有哪一種算法能夠適用于所有的網(wǎng)絡(luò)形式，并且在所有的網(wǎng)絡(luò)形式上具有很好的空間和時(shí)間復(fù)雜性。這些算法又具有各自的優(yōu)缺點(diǎn)。按照起點(diǎn)終點(diǎn)及路徑的數(shù)據(jù)和特征，最短路徑問(wèn)題可分為五種類型：兩個(gè)節(jié)點(diǎn)間的最短路徑、所有節(jié)點(diǎn)的最短路徑、K則最短路徑、實(shí)時(shí)最短路徑和指定必經(jīng)點(diǎn)的最短路徑問(wèn)題。本文選取Dijkstra算法，F(xiàn)lord算法兩種常見(jiàn)的算法，對(duì)兩者的算法分別進(jìn)行了描述，并且就其應(yīng)用進(jìn)行了舉例。同時(shí)本文還選取了其他算法作為補(bǔ)充，并將實(shí)際問(wèn)題通過(guò)最短路徑算法達(dá)成最優(yōu)的解決辦法。

2最短路 2.1最短路的定義 （1）最短路徑問(wèn)題是在加權(quán)圖的兩個(gè)節(jié)點(diǎn)之間找到權(quán)值最小的路徑，這是圖論的一種描述，也是圖論中的一個(gè)重要問(wèn)題。在現(xiàn)實(shí)生活中，我們可以看到最短路徑問(wèn)題的例子，最佳公交路線和出行路線的選擇;也可以用于軍事領(lǐng)域，作戰(zhàn)部隊(duì)行進(jìn)路線等問(wèn)題密切相關(guān)，在圖中找到最短路徑，對(duì)最短路徑問(wèn)題的研究和應(yīng)用具有重要的意義和實(shí)用價(jià)值。在路徑優(yōu)化問(wèn)題中，如果優(yōu)化指標(biāo)和距離相關(guān)性較強(qiáng)，但相關(guān)性較弱等因素，則將最短距離準(zhǔn)則考慮為最短路徑問(wèn)題。例如，當(dāng)選擇軍事路線時(shí)，如果起點(diǎn)和目的地之間存在多條路線，則當(dāng)預(yù)測(cè)概率中風(fēng)險(xiǎn)指數(shù)相等時(shí)，應(yīng)考慮最短路徑問(wèn)題。最短路徑問(wèn)題算法是圖論中的一個(gè)經(jīng)典問(wèn)題，為了找到兩個(gè)節(jié)點(diǎn)之間最短路徑的圖（由節(jié)點(diǎn)和路徑組成）。包括算法特定形式：為了確定起始點(diǎn)的最短路徑問(wèn)題-已知的起始節(jié)點(diǎn)，最短路徑問(wèn)題。為了確定終點(diǎn)的最短路徑問(wèn)題-與確定起點(diǎn)問(wèn)題相反，這個(gè)問(wèn)題對(duì)終端節(jié)點(diǎn)而言是已知的最短路徑問(wèn)題。在無(wú)向圖中，問(wèn)題與確定起點(diǎn)的問(wèn)題完全相同。在有向圖中，問(wèn)題等同于確定反轉(zhuǎn)所有路徑方向的起點(diǎn)的問(wèn)題。為了確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題，稱為起點(diǎn)和終點(diǎn)，兩個(gè)節(jié)點(diǎn)之間的最短路徑。全局最短路徑問(wèn)題-用于圖中所有最短路徑。圖（graph）是數(shù)據(jù)結(jié)構(gòu)和算法學(xué)中最強(qiáng)大的框架之一（或許沒(méi)有之一）。圖幾乎可以用來(lái)表現(xiàn)所有類型的結(jié)構(gòu)或系統(tǒng)，從交通網(wǎng)絡(luò)到通信網(wǎng)絡(luò)，從下棋游戲到最優(yōu)流程，從任務(wù)分配到人際交互網(wǎng)絡(luò)，圖都有廣闊的用武之地。圖視為一種由“頂點(diǎn)”組成的抽象網(wǎng)絡(luò)，網(wǎng)絡(luò)中的各頂點(diǎn)可以通過(guò)“邊”實(shí)現(xiàn)彼此的連接，表示兩頂點(diǎn)有關(guān)聯(lián)。在圖上任取兩頂點(diǎn)，分別作為起點(diǎn)（startvertex）和終點(diǎn)（endvertex），我們可以規(guī)劃許多條由起點(diǎn)到終點(diǎn)的路線。不會(huì)來(lái)來(lái)回回繞圈子、不會(huì)重復(fù)經(jīng)過(guò)同一個(gè)點(diǎn)和同一條邊的路線，就是一條“路徑”。兩點(diǎn)之間存在路徑，則稱這2個(gè)頂點(diǎn)是連通的（connected）。

路徑也有權(quán)重。路徑經(jīng)過(guò)的每一條邊，沿路加權(quán)重，權(quán)重總和就是路徑的權(quán)重（通常只加邊的權(quán)重，而不考慮頂點(diǎn)的權(quán)重）。在路網(wǎng)中，路徑的權(quán)重，可以想象成路徑的總長(zhǎng)度。在有向圖中，路徑還必須跟隨邊的方向。值得注意的是，一條路徑包含了頂點(diǎn)和邊，因此路徑本身也構(gòu)成了圖結(jié)構(gòu)，只不過(guò)是一種特殊的圖結(jié)構(gòu)。2.2最短路的常見(jiàn)算法 （1）松弛技術(shù)松弛操作：對(duì)每個(gè)頂點(diǎn)v∈V，都設(shè)置一個(gè)屬性d[v]，用來(lái)描述從源點(diǎn)s到v的最短路徑上權(quán)值的上界，成為最短路徑估計(jì)(Shortest-pathEstimate)，同時(shí)π[v]代表前趨。初始化之后，對(duì)所有v∈V，π[v]=NIL，對(duì)v∈V–{s}，有d[s]=0以及d[v]=∞。松弛一條邊（u,v），如果這條邊可以對(duì)最短路徑改進(jìn)，則更新d[v]和π[v]。一次松弛操作可以減小最短路徑估計(jì)的值d[v]，并更新v的前趨域π[v]（2）Dijkstra算法最經(jīng)典的算法是Dijkstra算法，它是一種單源最短路算法，其核心思想是貪心算法(GreedyAlgorithm)，Dijkstra算法由荷蘭計(jì)算機(jī)科學(xué)家Dijkstra發(fā)現(xiàn)，這個(gè)算法至今差不多已有50年歷史，但是因?yàn)樗姆€(wěn)定性和通俗性，到現(xiàn)在依然強(qiáng)健。另外，Dijkstra算法要求所有邊的權(quán)值非負(fù)。（3）Bellman-Ford算法能在一般情況下（存在負(fù)權(quán)邊的情況）下，解決單源最短路徑問(wèn)題。（4）SPFA算法采用一系列的松弛操作以得到從某一個(gè)節(jié)點(diǎn)出發(fā)到達(dá)圖中其它所有節(jié)點(diǎn)的最短路徑。

3相關(guān)算法 3.1Dijkstra算法描述設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑,就將其加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。Dijstra算法的基本操作是邊緣擴(kuò)展：如果存在從u到V的邊，則通過(guò)將u（V）添加到s到u的末尾，可以擴(kuò)展從s到V的最短路徑。這條路徑的長(zhǎng)度是d[u]+w（U，V）。如果這個(gè)值小于已知的d[v]的值，我們可以用當(dāng)前的d[v]中的值替換一個(gè)新的值。已經(jīng)執(zhí)行了擴(kuò)展的邊操作，直到所有的d[v]代表從s到v的最短路徑的代價(jià)。這個(gè)算法被適當(dāng)?shù)亟M織，以便當(dāng)d[u]達(dá)到它的最終值時(shí)，每個(gè)邊（U，V）是只延長(zhǎng)一次。該算法維護(hù)兩個(gè)頂點(diǎn)集合S和Q.集合S保留已經(jīng)是最短路徑頂點(diǎn)的所有已知d[v]值的值，而集合Q保留所有其他頂點(diǎn)。集合S的初始狀態(tài)為空，并且每一步都有一個(gè)從Q到S的頂點(diǎn)。所選頂點(diǎn)是具有最小d[u]值的Q的頂點(diǎn)。當(dāng)頂點(diǎn)u從Q傳遞到S時(shí)，算法擴(kuò)展了每個(gè)外邊緣（U，V）。3.2Dijkstra算法舉例圖3.1Dijkstra算法示例圖S=1。因?yàn)樗蠾ij=0，所以D（V1，V1）=0。此時(shí)，V1是帶有P標(biāo)記的點(diǎn)。現(xiàn)在研究V1（V1，V2，），（V1，V3和）（V1，V4）的三個(gè)弧。如果某人從V1開(kāi)始（V1，沿著V2）達(dá)到V2，則d（V1，V1）+w12=6單位成本;如果他從V1開(kāi)始（V1，沿V3）達(dá)到V3，則d（V1，V1）+w13=3單位成本;類似地，如果（V1，V4）到達(dá)V4，則d（V1，V1）+w14=1單位成本。由于min{D（V1，V1）+w12，D（V1，V1）+w13，D（V1，V1）+w14}=D（V1，+w14=1，V1），他可以斷言，從V4到V1必須是1個(gè)單元，即從V1到V4的最短路徑是（V1，V4），D（V1，V4）=1。這是因?yàn)槿魏螐腣1到V4P的道路，如果不是（V1，V4），它將從V1（V1，沿著V2）開(kāi)始到達(dá)V2，或者沿著（V1，V3）到達(dá)v3。但如前所述，當(dāng)他有6個(gè)單位或3個(gè)單位的成本時(shí)，無(wú)論他如何再次從V2或從V3到V4，所需的總成本小于1（因?yàn)樗蠾ij=0）。因此，D（V1，=1，V4），所以你可以使V4進(jìn)入P標(biāo)簽?，F(xiàn)在從V1和V4到電弧其余部分的角度來(lái)看，從V2開(kāi)始，分別從V1開(kāi)始（V1，沿V2（V1，V3））），成本為6和3，從V4開(kāi)始（V4，V6）沿V6方向，成本為D（V1，V4）+W46=1+10=11單位。對(duì)于min{D（V1，V1）+w12，D（V1，V1）+w13，D（V1，V4）+w46}=D（V1，V1）+w13=3。出于同樣的原因，從最短路徑的V1到V3是（V1，V3），D（V1，V3）=3。這可以使V3成為P標(biāo)簽，因此可以從V1到最短路徑點(diǎn)獲得重復(fù)的過(guò)程。3.3Floyd算法描述從矩陣A-1開(kāi)始，依次生成矩陣A0，A1，A2，……，An–1。如果已經(jīng)生成矩陣Ak–1，那么就可以生成Ak，因?yàn)閷?duì)于任意一對(duì)頂點(diǎn)i和j，一定滿足下面兩條規(guī)則中的一條：1）如果k不是路徑p的中間頂點(diǎn)，則p的所有中間頂點(diǎn)皆在{1，2，……，k–1}中，其路徑代價(jià)為Ak-1[i][j]。如果k是路徑p的中間頂點(diǎn)，那么該路徑由從i到k的路徑和從k到j(luò)的路徑兩部分構(gòu)成，由于這兩條子路徑上的頂點(diǎn)序號(hào)都不大于k–1，因此其路徑代碼分別為Ak–1[i][k]和Ak–1[k][j]。三重循環(huán)用于創(chuàng)建存儲(chǔ)每個(gè)節(jié)點(diǎn)最短距離的矩陣。弗洛伊德算法仍然使用圖的鄰接矩陣弧[n+1][n+1]來(lái)存儲(chǔ)加權(quán)有向圖。該算法的基本思想是：建立一個(gè)矩陣，其中對(duì)角元素等于0，其中一個(gè)（k）[i][j]路徑長(zhǎng)度頂點(diǎn)i的其他元素到頂點(diǎn)J，K說(shuō)操作步驟。當(dāng)開(kāi)始時(shí)，在任何兩個(gè)到邊權(quán)重的頂點(diǎn)之間作為路徑長(zhǎng)度，而不是當(dāng)路徑長(zhǎng)度無(wú)限時(shí)，當(dāng)K=0時(shí)，A（0）[i][j]=arcs[i][j]之后，逐漸嘗試在原始路徑中添加另一個(gè)頂點(diǎn)作為中間頂點(diǎn)，如果增加頂點(diǎn)，則得到的路徑比原來(lái)的路徑長(zhǎng)度縮短，這是替換原始路徑的新路徑，修改矩陣元素。3.4Floyd算法舉例圖3.2無(wú)向圖表3.1算法步驟Distk[1]distk[2]distk[3]MINA->B1371A->C13*1A->D3353A->C2262B->D*4*4A->D2462

4Dijkstra算法和Floyd算法在求最短路徑的異同Dijkstra算法是由最短路徑算法的路徑長(zhǎng)度產(chǎn)生的遞增順序，單個(gè)源的最短路徑，沒(méi)有負(fù)向權(quán)限。它適用于有向圖和無(wú)向圖。它的時(shí)效性好，時(shí)間復(fù)雜度為O（V*V+E）。它可以通過(guò)優(yōu)先級(jí)隊(duì)列進(jìn)行優(yōu)化，優(yōu)化后的時(shí)間復(fù)雜度優(yōu)化為0（v*lgn）。然而，由于遍歷了許多節(jié)點(diǎn)，算法的效率很低。Floyd算法應(yīng)用了動(dòng)態(tài)規(guī)劃算法。密集圖的效果最好，邊權(quán)重可以為負(fù)。該算法簡(jiǎn)單有效，由于三重環(huán)路結(jié)構(gòu)緊湊，對(duì)于稠密圖形，效率高于|V|Dijkstra算法。本實(shí)用新型具有易懂的優(yōu)點(diǎn)，可以計(jì)算任意兩節(jié)點(diǎn)之間的最短距離，編寫(xiě)簡(jiǎn)單的代碼。但時(shí)間復(fù)雜度高，不適合計(jì)算大量數(shù)據(jù)。

5其他常見(jiàn)算法5.1Ballman-Ford算法對(duì)于給定的帶權(quán)有向圖G=(V,E)，其源點(diǎn)為s，加權(quán)函數(shù)為w：E→R，，對(duì)該圖運(yùn)行Bellman-Ford算法后可以返回一個(gè)布爾值，表明圖中是否存在著一個(gè)從源點(diǎn)可達(dá)的權(quán)為負(fù)的回路。若存在這樣的回路，問(wèn)題無(wú)解；否則，算法產(chǎn)生最短路徑及其權(quán)值。求含負(fù)權(quán)圖的單源最短路徑算法，效率很低，但代碼很容易寫(xiě)。即進(jìn)行不停地松弛（relaxation），每次松弛把每條邊都更新一下，若n-1次松弛后還能更新，則說(shuō)明圖中有負(fù)環(huán)(即負(fù)權(quán)回路，本文最后有解釋)，無(wú)法得出結(jié)果，否則就成功完成。Bellman-ford算法有一個(gè)小優(yōu)化：每次松弛先設(shè)一個(gè)旗幟flag，初值為FALSE，若有邊更新則賦值為T(mén)RUE，最終如果還是FALSE則直接成功退出。Bellman-Ford算法能在更普遍的情況下（存在負(fù)權(quán)邊）解決單源點(diǎn)最短路徑問(wèn)題。對(duì)于給定的帶權(quán)（有向或無(wú)向）圖G=（V,E），其源點(diǎn)為s，加權(quán)函數(shù)w是邊集E的映射。對(duì)圖G運(yùn)行Bellman-Ford算法的結(jié)果是一個(gè)布爾值，表明圖中是否存在著一個(gè)從源點(diǎn)s可達(dá)的負(fù)權(quán)回路。若不存在這樣的回路，算法將給出從源點(diǎn)s到圖G的任意頂點(diǎn)v的最短路徑d[v]。1.初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值d[v]←+∞,d[s]←0;2.迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）。3.檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在d[v]中。5.2SPFA算法SPFA算法通過(guò)維護(hù)一個(gè)隊(duì)列，使得一個(gè)節(jié)點(diǎn)的當(dāng)前最短路徑被更新之后沒(méi)有必要立刻去更新其他的節(jié)點(diǎn)，從而大大減少了重復(fù)的操作次數(shù)。實(shí)現(xiàn)方法：建立一個(gè)隊(duì)列，初始時(shí)隊(duì)列里只有起始點(diǎn)，再建立一個(gè)表格記錄起始點(diǎn)到所有點(diǎn)的最短路徑（該表格的初始值要賦為極大值，該點(diǎn)到他本身的路徑賦為0）。然后執(zhí)行松弛操作，用隊(duì)列里有的點(diǎn)作為起始點(diǎn)去刷新到所有點(diǎn)的最短路，如果刷新成功且被刷新點(diǎn)不在隊(duì)列中則把該點(diǎn)加入到隊(duì)列最后。重復(fù)執(zhí)行直到隊(duì)列為空。判斷有無(wú)負(fù)環(huán)：如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)N次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖）。

6上述幾種算法優(yōu)缺點(diǎn)分析及比較優(yōu)點(diǎn)缺點(diǎn)適用情況Dijkstra算法可進(jìn)行優(yōu)化效率很低單源，無(wú)負(fù)權(quán)邊Floyd算法易懂時(shí)間復(fù)雜度高，不適合計(jì)算大量數(shù)據(jù)多源，無(wú)負(fù)權(quán)邊Ballman-Ford算法;單源問(wèn)題，可分析負(fù)環(huán)路單源，負(fù)權(quán)邊有無(wú)都可SPFA算法減少重復(fù)的操作，時(shí)效性好時(shí)間效率不穩(wěn)定維護(hù)一個(gè)隊(duì)列7最短路徑算法在具體情境中的應(yīng)用在工業(yè)生產(chǎn)中，設(shè)備更新問(wèn)題。一些公司使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)部門(mén)將決定是否購(gòu)買(mǎi)新設(shè)備，或者繼續(xù)使用舊設(shè)備。如果購(gòu)買(mǎi)新設(shè)備，將支付購(gòu)買(mǎi)成本;如果繼續(xù)使用舊設(shè)備，則需要支付維護(hù)費(fèi)用。最短路徑算法應(yīng)用于如何制定幾年的設(shè)備更新計(jì)劃，最低成本的總支付。在通道路線設(shè)計(jì)中，研究最優(yōu)路線選擇，根據(jù)通路建立網(wǎng)絡(luò)圖，運(yùn)用合適的最短路徑算法算出最優(yōu)解?；谒阉髀窂降男?zhǔn)確定最短路徑，即搜索索引。根據(jù)不同的最優(yōu)目標(biāo)，可以選擇不同屬性的部分。由于船舶與通道