弗洛伊德演算法是干什麼的

1. 弗洛伊德的演算法（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｝的最短路徑。

2. 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法

迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。

迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。

弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。

3. 弗洛伊德與地傑斯特拉演算法的區別

最大的區別是演算法的時間復雜度
弗洛伊德演算法的復雜度最低也是N的三次方 如果是競賽的話你用弗洛伊德很不幸 你會超時
但是地傑斯特拉演算法的復雜度就很低了可以達到期望logn級別 比N的三次方的演算法就快了很多
還有一個區別就是在做最短路問題的時候迪傑斯特拉演算法不適用於邊有負權值的圖
當碰到邊有負權時 你可以選擇SPFA演算法 這是迪傑斯特拉演算法的優化版 對稀疏圖有不錯的效果
順帶一提 SPFA是中國人優化的

4. 弗洛伊德演算法求出最短距離

（1）利用二維數組dist[i][j]記錄當前vi到vj的最短路徑長度，數組dist的初值等於圖的帶權鄰接矩陣;

（3）依次向S中加入v0,v1…vn-1，每加入一個頂點，對dist[i][j]進行一次修正：設S={v0,v1…vk-1}，加入vk，則dist(k)[i][j]=min{dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。

dist(k)[i][j]的含義：允許中間頂點的序號最大為k時從vi到vj的最短路徑長度。
dist(n-1)[i][j]就是vi到vj的最短路徑長度。

弗洛伊德最短距離演算法（FloydShortestPathAlgorithm）又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的演算法。該演算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。
中文名弗洛伊德最短距離演算法
外文名FloydShortestPathAlgorithm
所屬學科IT
所屬領域程序設計
簡介
最短路問題是網路最優化中一個基本而又非常重要的問題，這一問題相對比較簡單，在實際生產和生活中經常遇到，許多的網路最優化問題可以化為最短路問題，或者用最短路演算法作為其子程序.因此，最短路的用途已遠遠超出其表面意義迄今為止，所有最短路演算法都只對不含負迴路的網路有效，實際上對含有負迴路的網路，其最短路問題是NP困難的，因此本研究所討論的網路也不含負迴路.此外，如果將無向圖每條邊用兩條端點相同、方向相反的弧來代替，可以將其化為有向圖，因而不討論無向圖.本研究中未述及的術語、記號。
Floyd演算法是一種用於尋找給定加權圖中頂點間最短路徑的演算法，以1978年圖靈獎獲得者斯坦福大學計算機科學系教授RobertW．Floyd命名。Floyd演算法採用動態規劃的原理計算兩兩頂點間最短路徑，主要解決網路路由尋找最優路徑的問題。

5. Floyd演算法的優缺點分析

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

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

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

7. 跪求 弗洛伊德演算法 一個錯誤的解釋：

floyd演算法用以解決所有點對最短路徑。

floyd演算法基本思想是遞推，動態規劃。我們記 dp[j][k] 表示圖中頂點 i 到 j 的最短路徑，且該最短路徑中，所經過的中間頂點(不包括 i, j) 的范圍為 [1,k]，由此我們可以得到以下遞推式：

dp[j][k]= w[j] 如果 k== 0

dp[j][k]= min{ dp[k][k-1]+ dp[k][j][k-1] } 如果 k>= 1。

實際中，空間上我們可以減少一維。

floyd演算法同樣可以來解決一些其它問題

1) 有向圖的最小(或最大)環

這個問題答案其實就是自身到自身的最短路徑，運行完 floyd 後，對每個頂點取自身到自身距離的最小者。

2) 無向圖的最小環

根據以上的遞推式，dp[j][k] 表示 i 到 j 的最短路徑，且該最短路徑中，所經過的中間頂點(不包括 i, j) 的范圍為 [1,k]。

此時我們可以枚舉出頂點序列最大為 k+ 1 的所有最小環，如何枚舉：設與頂點序列最大的頂點 k+ 1 相連的兩個頂點為 x, y，x,y 須滿足 x, y<= k。這樣最小環構成為 邊<x,k+1> 邊<k+ 1, y> 及 x 到 y 的最短路徑。

Poj 1734 Sightseeing trip

#include <stdio.h>
#include <stdlib.h>

int const N= 110, inf= 5000000;
int mat[N][N], dist[N][N], pre[N][N], path[N], n, m, top= 0, p;

#define min(a,b) ((a)<(b)?(a):(b))

int main(){
scanf("%d%d",&n,&m );
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j ){
mat[j]= inf; dist[j]= inf; pre[j]= j; }
while( m-- ){
int u, v, d;
scanf("%d%d%d",&u,&v,&d);
mat[v]= min( mat[v], d );
mat[v]= mat[v];
dist[v]= mat[v]; dist[v]= mat[v];
}
int ans= inf;
for( int k= 1; k<= n; ++k ){
for( int x= 1; x< k; ++x )
for( int y= 1; y< x; ++y ){
if( mat[x][k]+ mat[k][y]+ dist[x][y]< ans ){
ans= mat[x][k]+ mat[k][y]+ dist[x][y];
top= 0; path[top++]= k; p= x;
while( p!= y ){
path[top++]= p; p= pre[p][y];
}
path[top++]= y;
}
}
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
if( dist[k]+ dist[k][j]< dist[j] ){
dist[j]= dist[k]+ dist[k][j];
pre[j]= pre[k]; }
}
if( top> 0 ){
printf("%d", path[0] );
for( int i= 1; i< top; ++i ) printf(" %d", path );
puts("");
}else puts("No solution.");

return 0;
}

8. 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兩點之間最短路徑所必須經過的點

9. 弗洛伊德演算法的姓氏

c語言文件讀寫操作褲缺薯代碼
演算法之「弗洛伊德（Floyd）演算法」

weixin_34239169
轉載
關注
0點贊·271人閱讀
弗洛伊德演算法
弗洛伊德（Floyd）演算法是 Robert W. Floyd（羅伯特·弗洛伊德）於胡者 1962 年發表在「Communications of the ACM」上，Robert W．Floyd 在 1978 年獲得了圖靈獎。用於從給定的加權圖中查找所有頂點間的最短路徑問題。作為該算扮卜法的結果，它將生成矩陣，該矩陣將表示從任何頂點到圖中所有其他頂點的最小距離。
弗洛伊德演算法步驟
1.根據輸入圖的二維數組初始化輸出 dist 二維數組。
2.利用中間頂點，逐個挑選所有頂點並更新所有最短路徑。
3.選擇頂點 k 作為中間頂點時，我們將頂點 {0,1,2，... k-1} 視為中間頂點，i、j 表示源頂點和目標頂點。
4.如果 k 不是從 i 到 j 的最短路徑中的中間頂點，我們保持 dist [i] [j]的值不變。
5.如果 k 是從 i 到 j 的最短路徑中的中間頂點，並且 dist[i][k] + dist[k][j] < dist[i][j]，則更新 dist[i][j] = dist[i][k] + dist[k][j]。