floyd優化演算法

① Floyd演算法的演算法過程

1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。
2，對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。
把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=無窮大。定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。
比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。

② floyd綆楁硶 鏄鍔ㄦ佽勫垝鐨勬濇兂鍚

1.瀹氫箟姒傝

Floyd-Warshall綆楁硶錛團loyd-Warshall algorithm錛夋槸瑙ｅ喅浠繪剰涓ょ偣闂寸殑鏈鐭璺寰勭殑涓縐嶇畻娉曪紝鍙浠ユｇ『澶勭悊鏈夊悜鍥炬垨璐熸潈鐨勬渶鐭璺寰勯棶棰橈紝鍚屾椂涔熻鐢ㄤ簬璁＄畻鏈夊悜鍥劇殑浼犻掗棴鍖呫侳loyd-Warshall綆楁硶鐨勬椂闂村嶆潅搴︿負O(N3)錛岀┖闂村嶆潅搴︿負O(N2)銆

2.綆楁硶鎻忚堪

1)綆楁硶鎬濇兂鍘熺悊錛

Floyd綆楁硶鏄涓涓緇忓吀鐨勫姩鎬佽勫垝綆楁硶銆傜敤閫氫織鐨勮璦鏉ユ弿榪扮殑璇濓紝棣栧厛鎴戜滑鐨勭洰鏍囨槸瀵繪壘浠庣偣i鍒扮偣j鐨勬渶鐭璺寰勩備粠鍔ㄦ佽勫垝鐨勮掑害鐪嬮棶棰橈紝鎴戜滑闇瑕佷負榪欎釜鐩鏍囬噸鏂板仛涓涓璇犻噴錛堣繖涓璇犻噴姝ｆ槸鍔ㄦ佽勫垝鏈瀵屽壋閫犲姏鐨勭簿鍗庢墍鍦錛

浠庝換鎰忚妭鐐筰鍒頒換鎰忚妭鐐筳鐨勬渶鐭璺寰勪笉澶栦箮2縐嶅彲鑳斤紝1鏄鐩存帴浠巌鍒癹錛2鏄浠巌緇忚繃鑻ュ共涓鑺傜偣k鍒癹銆傛墍浠ワ紝鎴戜滑鍋囪綝is(i,j)涓鴻妭鐐箄鍒拌妭鐐箆鐨勬渶鐭璺寰勭殑璺濈伙紝瀵逛簬姣忎竴涓鑺傜偣k錛屾垜浠媯鏌Dis(i,k) + Dis(k,j) < Dis(i,j)鏄鍚︽垚絝嬶紝濡傛灉鎴愮珛錛岃瘉鏄庝粠i鍒発鍐嶅埌j鐨勮礬寰勬瘮i鐩存帴鍒癹鐨勮礬寰勭煭錛屾垜浠渚胯劇疆Dis(i,j) = Dis(i,k) + Dis(k,j)錛岃繖鏍蜂竴鏉ワ紝褰撴垜浠閬嶅巻瀹屾墍鏈夎妭鐐筴錛孌is(i,j)涓璁板綍鐨勪究鏄痠鍒癹鐨勬渶鐭璺寰勭殑璺濈匯

2).綆楁硶鎻忚堪錛

a.浠庝換鎰忎竴鏉″崟杈硅礬寰勫紑濮嬨傛墍鏈変袱鐐逛箣闂寸殑璺濈繪槸杈圭殑鏉冿紝濡傛灉涓ょ偣涔嬮棿娌℃湁杈圭浉榪烇紝鍒欐潈涓烘棤絀峰ぇ銆 銆銆

b.瀵逛簬姣忎竴瀵歸《鐐 u 鍜 v錛岀湅鐪嬫槸鍚﹀瓨鍦ㄤ竴涓欏剁偣 w 浣垮緱浠 u 鍒 w 鍐嶅埌 v 姣斿繁鐭ョ殑璺寰勬洿鐭銆傚傛灉鏄鏇存柊瀹冦

3).Floyd綆楁硶榪囩▼鐭╅樀鐨勮＄畻----鍗佸瓧浜ゅ弶娉

鏂規硶錛氫袱鏉＄嚎錛屼粠宸︿笂瑙掑紑濮嬭＄畻涓鐩村埌鍙充笅瑙 濡備笅鎵紺

緇欏嚭鐭╅樀錛屽叾涓鐭╅樀A鏄閭繪帴鐭╅樀錛岃岀煩闃礟ath璁板綍u,v涓ょ偣涔嬮棿鏈鐭璺寰勬墍蹇呴』緇忚繃鐨勭偣

③ Floyd演算法是什麼

Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。
通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最後又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個後繼節點矩陣path來記錄兩點間的最短路徑。
採用的是(鬆弛技術)，對在i和j之間的所有其他點進行一次鬆弛。所以時間復雜度為O(n^3); 其狀態轉移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]} map[i,j]表示i到j的最短距離 K是窮舉i,j的斷點 map[n,n]初值應該為0，或者按照題目意思來做。
當然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路

④ 銆愬師鍒涖戠畻娉曠郴鍒椻斺斿洓縐嶆渶鐭璺綆楁硶錛欶loyd錛孌ijkstra錛孊ellman-Ford錛孲PFA

綆楁硶涔嬫棶錛氭帰緔㈠洓縐嶇粡鍏告渶鐭璺寰勭畻娉

⑤ Floyd演算法的優缺點分析

Floyd演算法適用於APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法，也要高於執行V次SPFA演算法。
優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單。
缺點：時間復雜度比較高，不適合計算大量數據。

⑥ 最短路徑演算法

最短路徑的演算法主要有三種：floyd演算法、Dijkstra演算法、Bellman-Ford(貝爾曼-福特)

一、floyd演算法

基本思想如下：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點X到B。所以，我們假設Dis(AB)為節點A到節點B的最短路徑的距離，對於每一個節點X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來，當我們遍歷完所有節點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。

三、Bellman-Ford(貝爾曼-福特)

演算法的流程如下：

給定圖G(V, E)（其中V、E分別為圖G的頂點集與邊集），源點s，

1.數組Distant[i]記錄從源點s到頂點i的路徑長度，初始化數組Distant[n]為, Distant[s]為0；

2.以下操作循環執行至多n-1次，n為頂點數：
對於每一條邊e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值；
若上述操作沒有對Distant進行更新，說明最短路徑已經查找完畢，或者部分點不可達，跳出循環。否則執行下次循環；

3.為了檢測圖中是否存在負環路，即權值之和小於0的環路。對於每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負環路，即是說該圖無法求出單源最短路徑。否則數組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度。

可知，Bellman-Ford演算法尋找單源最短路徑的時間復雜度為O(V*E).

⑦ floyd演算法能不能保證有最優解

Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。

演算法過程:

把圖用鄰接距陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。

定義一個距陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。
把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。

在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。
比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。