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演算法能不能保證有最優解
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直接相連。
⑶ 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]這條路
⑷ floyd判圈演算法
問題：如何檢測一個鏈表是否有環，如果有，那麼如何確定環的起點.
要求 : 空間復雜度為O(1), 時間復雜度為O(n).
假設一個有環鏈表如下圖: 利用floyd判圈演算法可以做到下面的三件事:
使用兩個指針slow和fast。兩個指針都從鏈表的起始處S開始。slow每次向後移動一步，fast每次激廳向後移動兩步。若在fast到達鏈表尾部明慎隱前slow與fast相遇了，就說明鏈表有環。
這里可以簡單的證明一下：反證法，假如沒有環，那麼slow永遠追不上fast，那麼在fast到達鏈表尾部前slow不會fast相遇了。若相遇了，鏈表就有環。
當slow和fast相遇時，slow和fast必定在環上，所以只要讓一者不動，另一者走一圈直到相遇，走過的節點數就是環的長度。
如圖所示，設AB=n, SA=m。設環的長度為L。
假設slow走過的節點數為i，那麼有：
i = m + n + a L a為slow繞過的環的圈數。
因為fast速度為slow的兩倍，所以相同時間走過的節點數為slow的兩倍，所以有：
2 i = m + n + b L b為fast繞過的環的圈數。
兩者做差有 : i = (b-a) L。
所以可知，fast和slow走過的距離是環的整數倍。
所以有m+n=L。
所以此時讓slow回到起點S，，fast仍然在B。
讓兩個指針以每次一步的速度往前走。
當走了m步時，可發現slow和fast正好都在A處，即是環的起點。
floyd判圈演算法是一個很有趣的演算法，在某些題目上用處很大，比如下面這個孝閉。
給出一個數組 nums 包含 n + 1 個整數，每個整數是從 1 到 n (包括邊界)，保證至少存在一個重復的整數。假設只有一個重復的整數，找出這個重復的數。
注意事項
對於這個題目
⑸ 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法
迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。
迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。
弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。
⑹ 弗洛伊德的演算法（Floyd』s algorithm ）
假設這個圖的weight matrix存在map[5][5]中，
for(intk=0;k<5;k++)
for(inti=0;i<5;i++)
for(intj=0;j<5;j++)if(i!=j){
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
}
處理完之後map[i][j]存的就是i，j之間的最短路徑長度。
簡單的說，當執行完一次最外層循環時，map記錄的時i，j之間允許使用中間節點｛0, ..., k｝的最短路徑。
⑺ 最短路徑演算法
最短路徑的演算法主要有三種：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).