幾種常用的最短路徑算法

1、簡(jiǎn)述幾種常用的最短路徑算法摘要：隨著社會(huì)的發(fā)展，最短路徑問(wèn)題在現(xiàn)實(shí)生活中占據(jù)的地位越來(lái)越重要。求解這一類問(wèn)題的方法有很多，包括Floyd算法、Dijkstra算法、BellmanFd算法、動(dòng)態(tài)規(guī)劃算法和智能優(yōu)化算法。其中較為常用的是Floyd算法、Dijkstra算法和BellmanFd算法。本文將簡(jiǎn)單介紹這三種最短路徑算法，通過(guò)比較各種方法的優(yōu)劣使對(duì)其有更進(jìn)一步的認(rèn)識(shí)和學(xué)習(xí)。關(guān)鍵字：最短路徑；最短路徑算法；Floyd算法；Dijkst

2、ra算法；BellmanFd算法隨著計(jì)算機(jī)科學(xué)的發(fā)展，人們生產(chǎn)生活效率要求的提高，最短路徑問(wèn)題逐漸成為計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科的一個(gè)研究熱點(diǎn)。也正因?yàn)樽疃搪窂絾?wèn)題在實(shí)際生產(chǎn)生活中應(yīng)用廣泛，優(yōu)化該算法和提高算法的求解效率具有重大的現(xiàn)實(shí)意義。1.最短路徑概述最短路徑問(wèn)題是指在一個(gè)賦權(quán)圖的兩個(gè)節(jié)點(diǎn)之間找出一條具有最小權(quán)的路徑，這是圖論的描述，也是圖論中研究的一個(gè)重要問(wèn)題。現(xiàn)實(shí)生活中我們可以看到這些最短路徑問(wèn)題的例子，公交車輛的最

3、優(yōu)行駛路線和旅游線路的選擇等；軍事領(lǐng)域中也有應(yīng)用，作戰(zhàn)部隊(duì)的行軍路線等問(wèn)題就與尋找一個(gè)圖的最短路徑密切相關(guān)，因此對(duì)最短路徑問(wèn)題的深入研究和廣泛應(yīng)用具有重要意義和實(shí)用價(jià)值。在線路優(yōu)化問(wèn)題中，如果優(yōu)化指標(biāo)與路程的相關(guān)性較強(qiáng)，而和其他因素相關(guān)性較弱時(shí)，即以最短路程為準(zhǔn)則，則考慮轉(zhuǎn)化為最短路徑問(wèn)題。比如軍事行軍線路選取時(shí)，假如從出發(fā)地到目的地之間有多種線路可以選取，危險(xiǎn)指數(shù)在預(yù)測(cè)概率相等時(shí)，就要考慮最短路徑問(wèn)題。2.最短路徑算法概述最短路徑算法

4、問(wèn)題是圖論研究中的一個(gè)經(jīng)典算法問(wèn)題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。算法具體的形式包括：確定起點(diǎn)的最短路徑問(wèn)題即已知起始結(jié)點(diǎn)，求最短路徑的問(wèn)題。確定終點(diǎn)的最短路徑問(wèn)題與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終結(jié)結(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)，求兩結(jié)點(diǎn)之間的最短路徑。全局最短路徑問(wèn)題求圖

5、中所有的最短路徑。3.Floyd算法3.1算法定義Floyd算法是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。Floyd算法的時(shí)間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。問(wèn)題描述：在無(wú)向圖G=(VE)中，假設(shè)每條邊E

6、[i]的長(zhǎng)度為w[i]，找到由頂點(diǎn)V0到其余各點(diǎn)的最短路徑。4.2算法描述4.2.1算法思想原理設(shè)G=(VE)是一個(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到

7、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)度。4.2.2算法過(guò)程描述a.初始時(shí)，S只包含源點(diǎn)，即S＝v，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U=其余頂點(diǎn)，若v與U中頂點(diǎn)u有邊，則正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則權(quán)值為∞。b.從U中選取一個(gè)距離v最小的頂

8、點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過(guò)頂點(diǎn)k）比原來(lái)距離（不經(jīng)過(guò)頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。4.3算法適用范圍⑴單源最短路徑；⑵有向圖和無(wú)向圖；⑶所有邊權(quán)非負(fù)。4.4算法實(shí)例圖2無(wú)向圖根據(jù)圖2，用Dijkstra算法找出以A為起點(diǎn)的單源最短路徑步