floyd演算法矩陣

⑴ 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演算法 是動態規劃的思想嗎

1.定義概覽
Floyd-Warshall演算法（Floyd-Warshall
algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。Floyd-Warshall演算法的時間復雜度為O(N3)，空間復雜度為O(N2)。
2.演算法描述
1)演算法思想原理：
Floyd演算法是一個經典的動態規劃演算法。用通俗的語言來描述的話，首先我們的目標是尋找從點i到點j的最短路徑。從動態規劃的角度看問題，我們需要為這個目標重新做一個詮釋（這個詮釋正是動態規劃最富創造力的精華所在）
從任意節點i到任意節點j的最短路徑不外乎2種可能，1是直接從i到j，2是從i經過若干個節點k到j。所以，我們假設Dis(i,j)為節點u到節點v的最短路徑的距離，對於每一個節點k，我們檢查Dis(i,k)
+
Dis(k,j)
<
Dis(i,j)是否成立，如果成立，證明從i到k再到j的路徑比i直接到j的路徑短，我們便設置Dis(i,j)
=
Dis(i,k)
+
Dis(k,j)，這樣一來，當我們遍歷完所有節點k，Dis(i,j)中記錄的便是i到j的最短路徑的距離。
2).演算法描述：
a.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。

b.對於每一對頂...
1.定義概覽
Floyd-Warshall演算法（Floyd-Warshall
algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。Floyd-Warshall演算法的時間復雜度為O(N3)，空間復雜度為O(N2)。
2.演算法描述
1)演算法思想原理：
Floyd演算法是一個經典的動態規劃演算法。用通俗的語言來描述的話，首先我們的目標是尋找從點i到點j的最短路徑。從動態規劃的角度看問題，我們需要為這個目標重新做一個詮釋（這個詮釋正是動態規劃最富創造力的精華所在）
從任意節點i到任意節點j的最短路徑不外乎2種可能，1是直接從i到j，2是從i經過若干個節點k到j。所以，我們假設Dis(i,j)為節點u到節點v的最短路徑的距離，對於每一個節點k，我們檢查Dis(i,k)
+
Dis(k,j)
<
Dis(i,j)是否成立，如果成立，證明從i到k再到j的路徑比i直接到j的路徑短，我們便設置Dis(i,j)
=
Dis(i,k)
+
Dis(k,j)，這樣一來，當我們遍歷完所有節點k，Dis(i,j)中記錄的便是i到j的最短路徑的距離。
2).演算法描述：
a.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。

b.對於每一對頂點
u
和
v，看看是否存在一個頂點
w
使得從
u
到
w
再到
v
比己知的路徑更短。如果是更新它。
3).Floyd演算法過程矩陣的計算----十字交叉法
方法：兩條線，從左上角開始計算一直到右下角
如下所示
給出矩陣，其中矩陣A是鄰接矩陣，而矩陣Path記錄u,v兩點之間最短路徑所必須經過的點

⑶ 求弗洛伊德演算法的詳細解釋~

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之間的最短路徑

⑷ 怎麼根據Floyd演算法 從多個頂點中選出幾個，使其他點到選出點距離最短

先用floyd求出距離矩陣D，即以下代碼中的矩陣B。
以下matlab程序為從12個點中選出3點，可以此類推。

clear all;
A=[combntns(1:12,3)]; %列出12個居民點選3個繳費點的所有情況。
for i=1:nchoosek(12,3) %for……end， 循環，計算以上列出所有情況下所有居民需要行走的總路程！
A2=A(i,:);
A3=A2(1,1); %讀取選取3個居民點
A4=A2(1,2);
A5=A2(1,3);
People=[15 10 12 18 5 24 11 16 13 22 19 20]; %每個居民點的人數的矩陣。
B=[
0 15 37 55 24 60 18 33 48 40 58 67;
15 0 22 40 38 52 33 48 42 55 61 61;
37 22 0 18 16 30 43 28 20 58 39 39;
55 40 18 0 34 12 61 46 24 62 43 34;
24 38 16 34 0 36 27 12 24 49 37 43;
60 52 30 12 36 0 57 42 12 50 31 22;
18 33 43 61 27 57 0 15 45 22 40 61;
33 48 28 46 12 42 15 0 30 37 25 46;
48 42 20 24 24 12 45 30 0 38 19 19;
40 55 58 62 49 50 22 37 38 0 19 40;
58 61 39 43 37 31 40 25 19 19 0 21;
67 61 39 34 43 22 61 46 19 40 21 0 ;
]; %居民到其他居民點所有最短的距離。

B1=B(:,A3); %居民點到所選的繳費點的理論最短距離。
B2=B(:,A4);
B3=B(:,A5);
C=[B1 B2 B3];
D=sort(C,2);
Shortjourney=D(:,1); %每位居民選擇繳費點後需要行走的最短路程。
Sum(i)=People*Shortjourney; %所有居民所要行走的路程總和。
end
E=[reshape(Sum,nchoosek(12,3),1)]; %將以上得到的數組轉為矩陣。
minposition=find(E==min(E)); %找出最小值在矩陣的位置。
A=[combntns(1:12,3)]; %A的順序與E的一致！
position=A(minposition,:) %最佳的繳費點的選擇。

⑸ 用你熟悉的語言實現Floyd演算法，對於具有下面權重矩陣的有向圖求解完全最短路徑，截圖給出運行結果

Floyd的關鍵是三重循環和鬆弛式d[i][j] = min(d[i][j], d[i][k] + d[k][j])，代碼和注釋如下所示：

#include<bits/stdc++.h>
usingnamespacestd;

constintINF=1000000000;

constintn=5;

//鄰接矩陣
intd[][n]={
{0,2,INF,1,8},
{6,0,3,2,INF},
{INF,INF,0,4,INF},
{INF,INF,2,0,3},
{3,INF,INF,INF,0}
};
intmain()
{
//floyd
for(intk=0;k<n;++k)
for(inti=0;i<n;++i)
for(intj=0;j<n;++j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

//輸出結果
for(inti=0;i<n;++i){
for(intj=0;j<n;++j){
if(j>0)printf("");
if(d[i][j]==INF)printf("INF");
elseprintf("%3d",d[i][j]);
}
puts("");
}
return0;
}

運行結果圖：