幾種常用的最短路徑算法

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

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

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

4、問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。算法具體的形式包括：確定起點的最短路徑問題即已知起始結(jié)點，求最短路徑的問題。確定終點的最短路徑問題與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。確定起點終點的最短路徑問題即已知起點和終點，求兩結(jié)點之間的最短路徑。全局最短路徑問題求圖

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

6、[i]的長度為w[i]，找到由頂點V0到其余各點的最短路徑。4.2算法描述4.2.1算法思想原理設(shè)G=(VE)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑就將加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到

7、S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。4.2.2算法過程描述a.初始時，S只包含源點，即S＝v，v的距離為0。U包含除v外的其他頂點，即:U=其余頂點，若v與U中頂點u有邊，則正常有權(quán)值，若u不是v的出邊鄰接點，則權(quán)值為∞。b.從U中選取一個距離v最小的頂

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