弗洛伊德演算法矩陣

『壹』 每一對頂點之間的最短路徑是什麼

每一對頂點之間的最短路徑是指對於給定的帶權有向圖G＝（v，E），要對G中任意一對頂點有序對（vi，vj）（vi≠vj），找出vi到vj的最短距離和vj到vi的最短距離。

解決此問題的一個有效方法是：輪流以每一個頂點為源點，重復執行Dijkstra演算法n次，即可求得有向圖G＝（v，E）中每一對頂點間的最短路徑，總的時間復雜度為0（n2）。

弗洛伊德（Floyd）提出了另一個求任意兩頂點之間最短路徑的演算法，雖然其時間復雜度也是0（n2），但演算法形式更為簡明，易於理解與編程。

1.弗洛伊德演算法的思想弗洛伊德演算法是從圖的鄰接矩陣開始，按照頂點v0，v1，v2，v2，…，vn的次序，分別以每個頂點vk（0≤k＜n）作為新考慮的中間點，在第k－1次運算D（k－1）的基礎上，求出每一對頂點之間vi到vj的最短路徑長度D（k）［i］［j］，計算公式為：

D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝重復執行n次後，D（k）［i］［j］中保留的值就是每對頂點的vi到vj的最短路徑長度。

2.弗洛伊德演算法的步驟（1）從圖的帶權鄰接矩陣G．arcs［］［］開始，即D（－1）＝arcs［］［］，每次以上一次D（k－1）為基礎，用公式D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝計算出D（k）［i］［j］的值，即D（k－1）［i］［k］＋D（k－1）［k］［j］＜D（k－1）［i］［j］才修改，若D（k）［i］［j］修改過，則相應的路徑P（k）［i］［j］也要作相應的修改，即P（k）［i］［j］＝P（k－1）［i］［k］＋P（k－1）［k］［j］。

（2）重復上述過程n次後，D（k）［i］［j］中保存的就是每一對頂點的最短路徑長度，P（k）［i］［j］中保存的就是每一對頂點的最短路徑。

說明：從計算公式可以看出，i＝j是對角線上的元素；i＝k是i行上的元素；j＝k是j列上的元素，這些特殊的頂點不用計算，保留原來的數據值。因此，計算的數據元素減少了很多。

『貳』 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，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。
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演算法計算最短距離時，賦權鄰接矩陣怎麼算

Model:
!2個工廠，3個中轉站及4個客戶的運輸問題;
sets:
plant/A,B/:proce;
warhouse/x,y,z/;
costomer/1..4/:require;
link(plant, warhouse,costomer):poss,cost,x;
endsets
data:
proce=9,8;
require=3,4,3,5;
!鄰接矩陣;
poss = 1 1 0 0 !A-x-1,A-x-2,A-x-3,A-x-4;
1 1 1 0 !A-y-1,A-y-2,A-y-3,A-y-4;
0 0 0 0 !A-z-1,A-z-2,A-z-3,A-z-4;
0 1 0 0 !B-x-1,B-x-2,B-x-3,B-x-4;
1 1 1 0 !B-y-1,B-y-2,B-y-3,B-y-4;
0 1 1 1; !B-z-1,B-z-2,B-z-3,B-z-4;
!賦權矩陣;
cost=6 8 0 0
11 8 9 0
0 0 0 0
8 10 0 0
10 7 8 0
0 10 9 6;
enddata
!目標函數;
min=@sum(link:poss*cost*x);
!約束條件;
@for(plant(i):@sum(warhouse(j): @sum(costomer(k):poss(i,j,k)*x(i,j,k)))<proce(i));
!對於廠家I，運出的從」I-J-K」的運量不超過該廠的產量;
@for(costomer(k) :@sum(plant(i):@sum(warhouse(j): poss(i,j,k)*x(i,j,k)))=require(k));
! 對於客戶K，運入的從」I-J-K」的運量不超過該客戶的需求量;
end
①鄰接矩陣，兩個廠家，則分兩組；3個中轉站，則每組3行；即共有2*3=6行；
第一組指的是從「廠家A」運出的，第二組指的是從「廠家B」運出的．
第一行表示通過中轉站X，第二行表示通過中轉站Y，第三行表示通過中轉站Z；
第一列表示到達客戶1，第二列表示到達客戶2，第三列表示到達客戶3，第4列表示到達客戶4．
如poss24屬於第一組的第2行第4列的元素，則表示從A-y-4的運輸情況．
②賦權矩陣，指的是相應的線路對應的權重和(運費之和).

『伍』 Floyd演算法中的矩陣就是鄰接矩陣么

是的。鄰接矩陣。存儲聯通狀態的。

『陸』 floyd如何判斷有多條最短路徑

1.定義概覽
Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。注意該演算法要求圖中不存在負權邊。
問題描述：在無向圖 G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）

2.演算法描述
1)演算法思想：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
2)演算法步驟：
a.初始時，S只包含源點，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即:U={其餘頂點}，若v與U中頂點u有邊，則<u,v>正常有權值，若u不是v的出邊鄰接點，則<u,v>權值為∞。
b.從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。
c.以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值的頂點k的距離加上邊上的權。
d.重復步驟b和c直到所有頂點都包含在S中。

執行動畫過程如下圖

3.演算法代碼實現：

const int MAXINT = 32767;
const int MAXNUM = 10;
int dist[MAXNUM];
int prev[MAXNUM];

int A[MAXUNM][MAXNUM];

void Dijkstra(int v0)
{
bool S[MAXNUM]; // 判斷是否已存入該點到S集合中
int n=MAXNUM;
for(int i=1; i<=n; ++i)
{
dist[i] = A[v0][i];
S[i] = false; // 初始都未用過該點
if(dist[i] == MAXINT)
prev[i] = -1;
else
prev[i] = v0;
}
dist[v0] = 0;
S[v0] = true;
for(int i=2; i<=n; i++)
{
int mindist = MAXINT;
int u = v0; // 找出當前未使用的點j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!S[j]) && dist[j]<mindist)
{
u = j; // u保存當前鄰接點中距離最小的點的號碼
mindist = dist[j];
}
S[u] = true;
for(int j=1; j<=n; j++)
if((!S[j]) && A[u][j]<MAXINT)
{
if(dist[u] + A[u][j] < dist[j]) //在通過新加入的u點路徑找到離v0點更短的路徑
{
dist[j] = dist[u] + A[u][j]; //更新dist
prev[j] = u; //記錄前驅頂點
}
}
}
}

4.演算法實例
先給出一個無向圖

用Dijkstra演算法找出以A為起點的單源最短路徑步驟如下

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

相應計算方法如下：

最後A3即為所求結果

3.演算法代碼實現

typedef struct
{
char vertex[VertexNum]; //頂點表
int edges[VertexNum][VertexNum]; //鄰接矩陣,可看做邊表
int n,e; //圖中當前的頂點數和邊數
}MGraph;

void Floyd(MGraph g)
{
int A[MAXV][MAXV];
int path[MAXV][MAXV];
int i,j,k,n=g.n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
}

『柒』 matlab floyd 演算法注釋

A矩陣是鄰接矩陣，對角線上為o，其餘位置數字表示的是兩點之間距離，比如A(1,2)=2,表示從第一個點到第二個點的距離為2.inf是無窮大的意思，這里表示沒有直接溝通這兩點的路。
n=length(D);設定n為D矩陣的長度。
接下來的兩重循環，得到的R矩陣是n*n的矩陣，它每個數據表示的是路徑，比如：R(1,3)=1;表示路徑為：1-1-3.這里是初始化路徑了。
後面的三重循環是floyd演算法的關鍵所在，就是更新路線了。裡面的那個判斷指的是：
假設有3個點，1
2
3；如果我從1-2-3之間總距離小於1-3的距離，那麼我R(1,3)=2；這就是選取更近的路線了。
最後的兩個判斷是為了不讓曾經走過的點再次被遍歷。就是不回頭的意思了，這個一般都可以忽略了，你照打上去就是了。
不知道這樣的解釋你是否滿意。

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

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演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。

演算法過程:

把圖用鄰接距陣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求出的path矩陣怎麼看

這是一個我寫的Floyd演算法的程序。w是圖的鄰接矩陣需要事先輸入並保存在工作空間中，調用方法為：[D,path]=floyd(w)。給出的結果D為路徑的鄰接矩陣，path為路徑所經過的端點順序。

程序為：
<pre t="code" l="cpp">function [D,path]=floyd(w)
%D R a
n=size(w,1);
%設初值
D=w;
path=zeros(n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
%迭代，更新D path
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k);
end
end
end
end