弗洛伊德演算法

『壹』 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]這條路

『貳』 最短路徑的弗洛伊德演算法我曾經想出不嚴格的證明，不滿意，嚴格的數學證明，我無法想出來，如何得到

看下於丹講的論語 絕對對你管用 要用心去領會《論語》心得(一)《天地人之道》 mms://winmedia.cctv/jiajiangtan/2006/11/jiajiangtan_300。

『叄』 求弗洛伊德演算法的詳細解釋~

floyd演算法思想：1，構建一個鄰接矩陣存儲任意兩點之間的權值如圖D0.

2、例如求v1,v4之間的最短路徑。先增加v2做中間頂點，D[1][4]=∞。if（D[1][4]>D[1][2]+D[2]4]）=6+4）D[1][4]=10;這樣就可以了。

3、如不能在離得較遠的兩點(例v1,v9）直接得到上述可以滿足if的中間點，則跟據你書本的代碼可以先構建原點到中間點的最短路徑，繼而就可以求得vi,v9之間的最短路徑

『肆』 弗洛伊德演算法

通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
從圖的帶權鄰接矩陣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』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｝的最短路徑。

『柒』 迪傑斯特拉演算法和弗洛伊德演算法有什麼區別

帶權的無向圖的最短路徑又叫最小生成樹，Prim演算法和Kruskal演算法；帶權的有向圖的最短路徑演算法有迪傑斯特拉演算法和佛洛依德演算法；

『捌』 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,2,...,k的最短距離，當1,2,...,k擴展到所有頂點時，演算法解出任意一對頂點間的最短距離，故順序自然是：
for(k=1;k<n;++k)
//枚舉任意一對頂點
由其狀態轉移方程來看，這個演算法的順序也很清晰，應該是先計算較小的k時任意ij之間的最短距離：
dij(k) = wij 如果k=0
min(dij(k-1),dik(k-1)+dkj(k-1)) 如果k>=1
其中i,j表示點對，k表示第1,2,...,k時的最短路徑

『拾』 Floyd演算法的演算法描述

a)初始化：D[u,v]=A[u,v]
b)For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
c)演算法結束：D即為所有點對的最短路徑矩陣