弗洛伊德算法（Floyd）簡介

Floyd算法適用于解決求最短路徑問題，相比于Digkstra算法思路更加簡單，更容易理解，但是效率會明顯低很多，可以作為初步學習的一種方法。

目錄

• 弗洛伊德算法（Floyd）簡介
• 主要思想
• • 具體步驟
  • • 具體例題
    • • 輸出最短路徑

主要思想

主要的想法就是創建一個矩陣用于記錄最短距離，如果需要求最短距離的路徑的話則需要創建另外一個矩陣用于記錄路徑，矩陣中放置中介點即可。

具體步驟

1.在主函數中創建一個矩陣，存儲輸入的兩點間的距離。
2.在Floyd函數中，初始化記錄最短距離的矩陣和記錄中介點的矩陣。初始化之后將主函數的矩陣復制給記錄最短距離的矩陣。
3.用三層循環不斷更新最短距離。
以上僅為簡要介紹，具體過程結合實例介紹。

具體例題

Problem Description：
某省自從實行了很多年的暢通工程計劃后，終于修建了很多路。不過路多了也不好，每次要從一個城鎮到另一個城鎮時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。

現在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離。

Input
本題目包含多組數據，請處理到文件結束。
每組數據第一行包含兩個正整數N和M(0<N<200,0<M<1000)，分別代表現有城鎮的數目和已修建的道路的數目。城鎮分別以0～N-1編號。
接下來是M行道路信息。每一行有三個整數A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮A和城鎮B之間有一條長度為X的雙向道路。
再接下一行有兩個整數S,T(0<=S,T<N)，分別代表起點和終點。

Output
對于每組數據，請在一行里輸出最短需要行走的距離。如果不存在從S到T的路線，就輸出-1.

Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2

Sample Output
2
-1

#include<iostream>using namespace std;#define MAXN 200
#define INF 10000000class Path
{public:int vexnum;       //點的個數 int edgnum;       //邊數 int matirx[MAXN][MAXN];      //點間的距離			
};int D[MAXN][MAXN];void Floyd(Path G)
{int v, w, k;//初始化floyd算法的矩陣 for(v = 0; v < G.vexnum; v++){for(w = 0; w < G.vexnum; w++){D[v][w] = G.matirx[v][w];}}for(k = 0; k < G.vexnum; k++){for(v = 0; v < G.vexnum; v++){for(w = 0; w < G.vexnum; w++){if(D[v][w] > (D[v][k] + D[k][w])){D[v][w] = D[v][k] + D[k][w];//更新最小路徑 }}}}
}int main()
{int N, M;while(~scanf("%d%d",&N,&M)){Path G;G.vexnum = N;G.edgnum = M;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){if(i == j)G.matirx[i][j] = 0;elseG.matirx[i][j] = INF;}}int s,e,l;for(int i = 0; i < M; i++){cin >> s >> e >> l;if(G.matirx[s][e] > l){G.matirx[s][e] = l;G.matirx[e][s] = l; }}Floyd(G);int st, en;cin >> st >> en;if(D[st][en] >= INF)cout << -1 << endl;elsecout << D[st][en] << endl;}return 0;
}

該代碼主要有以下幾個部分：
1.這個類用于儲存了點的個數，輸入邊的條數，以及各點間的距離。這里當然可以不使用類，直接使用全局變量也可以！

2.
這個主函數中的類負責記錄輸入的所有信息。第一個for循環用于初始化矩陣，同一個點的距離是0，其它的則是無限大（相對于出現的數據）。第二個for循環用于記錄輸入的點間的距離，輸入時需判斷是否為兩點間最短的距離，因為兩點間的路徑可能不止一條。

3.
該部分首先將主函數中的矩陣復制給D矩陣。三重循環中，k代表的是中介點，v是起點，w是終點，三重循環足以遍歷所有的情況，并完善矩陣。則各點間的距離全部記錄在D矩陣中，沒有路徑到達的兩點間的距離是無窮大。

當然，以上僅為求出最短距離，路徑則需要另外加上一個記錄中介點的矩陣。 詳見下解。

輸出最短路徑

#include<iostream>using namespace std;#define MAXN 200
#define INF 10000000class Path
{public:int vexnum;       //點的個數 int edgnum;       //邊數 int matirx[MAXN][MAXN];      //點間的距離		
};int D[MAXN][MAXN];
int P[MAXN][MAXN];       //新加入的矩陣用于記錄中介點void Floyd(Path G)
{int v, w, k;//初始化floyd算法的兩個矩陣 for(v = 0; v < G.vexnum; v++){for(w = 0; w < G.vexnum; w++){D[v][w] = G.matirx[v][w];P[v][w] = w;        //中介點的初始化}}for(k = 0; k < G.vexnum; k++){for(v = 0; v < G.vexnum; v++){for(w = 0; w < G.vexnum; w++){if(D[v][w] > (D[v][k] + D[k][w])){D[v][w] = D[v][k] + D[k][w];//更新最小路徑 P[v][w] = k;                //更新中介點}}}}
}void PP(int v, int w)         //路徑輸出函數
{while( P[v][w] != w){PP(v,P[v][w]);cout << P[v][w] << "->" ;return;}return;
}int main()
{int N, M;while(~scanf("%d%d",&N,&M)){Path G;G.vexnum = N;G.edgnum = M;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){if(i == j)G.matirx[i][j] = 0;elseG.matirx[i][j] = INF;}}int s,e,l;for(int i = 0; i < M; i++){cin >> s >> e >> l;if(G.matirx[s][e] > l){G.matirx[s][e] = l;G.matirx[e][s] = l; }}Floyd(G);int st, en;cin >> st >> en;if(D[st][en] >= INF)cout << -1 << endl;else{cout << D[st][en] << endl;cout << st << "->";PP(st,en);cout << en << endl;}    }return 0;
}

可見，上述代碼中的變化是多了一個矩陣并且初始化了中介點，在更新最短路徑的同時更新中介點。另外便是用遞歸輸出了路徑的中間過程，但要注意首尾需要自己加上。

總結

以上是生活随笔為你收集整理的弗洛伊德算法（Floyd）简介的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。