圖-弗洛伊德(FloydWarshall)算法詳解(含全部代碼)

程序員社區 2022-01-07 08:09:32 阅读数:832

弗洛伊德 洛伊 floydwarshall 算法

目錄

適用條件

基本操作函數

功能實現函數

測試使用圖

算法講解

初始化

迭代

弗洛伊德算法代碼

全部代碼

實驗結果

最短路徑算法比較


適用條件

圖中可以有負權,但不能有負圈(圈中弧或邊的權值之和小於0)

基本操作函數

  • InitGraph(Graph &G)             初始化函數 參數:圖G 作用:初始化圖的頂點錶,鄰接矩陣等
  • InsertNode(Graph &G,VexType v) 插入點函數 參數:圖G,頂點v 作用:在圖G中插入頂點v,即改變頂點錶
  • InsertEdge(Graph &G,VexType v,VexType w) 插入弧函數 參數:圖G,某弧兩端點v和w 作用:在圖G兩點v,w之間加入弧,即改變鄰接矩陣
  • Adjancent(Graph G,VexType v,VexType w) 判斷是否存在弧(v,w)函數 參數:圖G,某弧兩端點v和w 作用:判斷是否存在弧(v,w)
  • BFS(Graph G, int start) 廣度遍曆函數 參數:圖G,開始結點下標start 作用:寬度遍曆
  • DFS(Graph G, int start) 深度遍曆函數(遞歸形式)參數:圖G,開始結點下標start 作用:深度遍曆
  • Dijkstra(Graph G, int v)  最短路徑 - Dijkstra算法 參數:圖G、源點v
  • Bellman_Ford(Graph G, int v)  最短路徑 - Bellman_Ford算法  參數:圖G、源點v 作用:計算不含負圈圖的最短路徑 返回是否有圈
  • Floyd_Wallshall(Graph G)    最短路徑 - Floyd_Wallshall算法  參數:圖G 作用:計算不含負圈圖的最短路徑 返回是否有圈

功能實現函數

  • CreateGraph(Graph &G) 創建圖功能實現函數 參數:圖G  InsertNode 作用:創建圖
  • BFSTraverse(Graph G)  廣度遍曆功能實現函數 參數:圖G 作用:寬度遍曆
  • DFSTraverse(Graph G)  深度遍曆功能實現函數 參數:圖G 作用:深度遍曆
  • Shortest_Dijkstra(Graph &G) 調用最短路徑-Dijkstra算法 參數:圖G、源點v
  • Shortest_Bellman_Ford(Graph &G) 調用最短路徑- - Bellman_Ford算法  參數:圖G
  • Shortest_Floyd_Wallshall(Graph &G) 調用最短路徑- - Floyd_Wallshall算法  參數:圖G

測試使用圖

測試使用圖

算法講解

初始化

錶格行為i,列為j。D及P後小括號內的值為迭代次數。

D矩陣主對角線為0,其餘與鄰接矩陣相同。

P矩陣存-1,在輸出最短路徑時作為遞歸出口。

迭代

D矩陣的狀態轉移方程:D(m)[i][j]=min{D(m-1)[i][j],D(m-1)[i][k]+D[k][j]},0<<k<<n-1,其中,m為迭代次數,n為節點個數。

思路:添加一個點Vk,找到Vk的入弧Vi->Vk,再找到Vk的出弧,Vk->Vj,比較D[i][j]與D[i][k]+D[k][j]的大小。

若D矩陣有更新,則對應P矩陣的值為更新處最短路徑第一條弧的終點

D(1)

0 4 -3
-3 0 -7
10 0 3
5 6 6 0

P(1)

-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

 D(2)

0 4 -3
-3 0 -7
10 0 3
5 6 2 0

加入點V0,V0的入弧有V1->V0與V3->V0,出弧有V0->V1與V0->V2

經比較D(1)[3][2]>D(1)[3][0]+D(1)[0][2],6>5-3=2,所以,將6更新為2。

P(2)

-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 0 -1

P(2)[3][2]由P(1)[3][2]改為0,因為最短路徑為V3->V0->V2,第一條弧的終點為V0。

D(3)

0 4 -3
-3 0 -7
7 10 0 3
3 6 -1

0

 加入點V1,V1入弧有V0->V1,V2->V1以及V3->V1,出弧有V1->V2,V1->V0

經比較,D(2)[2][0]>D(2)[2][1]+D(2)[1][0],∞>10-3=7,所以,將∞更新為7。

            D(2)[3][0]>D(1)[3][1]+D(2)[1][0],5>6-3=3,所以,將5更新為3。

            D(2)[3][2]>D(1)[3][1]+D(2)[1][2],2>6-7=-1,所以,將2更新為-1。

P(3)

-1 -1 -1 -1
-1 -1 -1 -1
1 -1 -1 -1
1 -1 1 -1

P(3)[2][0]改為1,因為最短路徑為V2->V1->V0,第一條弧的終點為V1。

P(3)[3][0]改為1,因為最短路徑為V3->V1->V0,第一條弧的終點為V1。

P(3)[3][2]改為1,因為最短路徑為V3->V1->V2,第一條弧的終點為V1。

下面的由讀者根據原理及矩陣自己補充,加深印象。

D(4)

0 4 -3 0
-3 0 -7 -4
7 10 0 3
3 6 -1

0

P(4)

-1 -1 -1 2
-1 -1 -1 2
1 -1 -1 -1
1 -1 1 -1

D(5)

0 4 -3 0
-3 0 -7 -4
6 9 0 3
3 6 -1

0

P(5)

-1 -1 -1 2
-1 -1 -1 2
3 3 -1 -1
1 -1 1 -1

注意:弗洛伊德算法的最短路徑在輸出時不是倒著的,我們記錄的是第一條弧的終點。例如,p[2][0]=3,P[3][0]=1,P[1][0]=-1,

則V[2]到V[0]的最短路徑為2->3->1->0,值為6。也就是看P矩陣的列,這是與前面兩篇最短路徑算法不同的地方,需注意。

弗洛伊德算法代碼

//最短路徑 - Floyd_Wallshall算法 參數:圖G 作用:計算不含負圈圖的最短路徑 返回是否有圈bool Floyd_Wallshall(Graph G){ //初始化 for (int i = 0; i<G.vexnum; i++) for (int j = 0; j < G.vexnum; j++) { if (i == j)F_D[i][j] = 0; else F_D[i][j] = G.Edge[i][j]; P[i][j] = -1; } //初始化結束,開始迭代 for(int k=0;k<G.vexnum;k++) for (int i = 0; i<G.vexnum; i++) for (int j = 0; j<G.vexnum; j++) if (F_D[i][j] > F_D[i][k] + F_D[k][j]) { F_D[i][j] = F_D[i][k] + F_D[k][j]; P[i][j] = k; } bool flag = true; for (int i = 0; i < G.vexnum; i++) for (int j = 0; j < G.vexnum; j++) if (i==j&&F_D[i][j] < 0) { flag = false; break; } return flag;}

全部代碼

/*Project: 圖-最短路徑-Bellman-Ford算法(可含有負權弧)Date: 2019/10/24Author: Frank Yu基本操作函數:InitGraph(Graph &G) 初始化函數 參數:圖G 作用:初始化圖的頂點錶,鄰接矩陣等InsertNode(Graph &G,VexType v) 插入點函數 參數:圖G,頂點v 作用:在圖G中插入頂點v,即改變頂點錶InsertEdge(Graph &G,VexType v,VexType w) 插入弧函數 參數:圖G,某弧兩端點v和w 作用:在圖G兩點v,w之間加入弧,即改變鄰接矩陣Adjancent(Graph G,VexType v,VexType w) 判斷是否存在弧(v,w)函數 參數:圖G,某弧兩端點v和w 作用:判斷是否存在弧(v,w)BFS(Graph G, int start) 廣度遍曆函數 參數:圖G,開始結點下標start 作用:寬度遍曆DFS(Graph G, int start) 深度遍曆函數(遞歸形式)參數:圖G,開始結點下標start 作用:深度遍曆Dijkstra(Graph G, int v) 最短路徑 - Dijkstra算法 參數:圖G、源點vBellman_Ford(Graph G, int v) 最短路徑 - Bellman_Ford算法 參數:圖G、源點v 作用:計算不含負圈圖的最短路徑 返回是否有圈Floyd_Wallshall(Graph G) 最短路徑 - Floyd_Wallshall算法 參數:圖G 作用:計算不含負圈圖的最短路徑 返回是否有圈功能實現函數:CreateGraph(Graph &G) 創建圖功能實現函數 參數:圖G InsertNode 作用:創建圖BFSTraverse(Graph G) 廣度遍曆功能實現函數 參數:圖G 作用:寬度遍曆DFSTraverse(Graph G) 深度遍曆功能實現函數 參數:圖G 作用:深度遍曆Shortest_Dijkstra(Graph &G) 調用最短路徑-Dijkstra算法 參數:圖G、源點vShortest_Bellman_Ford(Graph &G) 調用最短路徑- - Bellman_Ford算法 參數:圖GShortest_Floyd_Wallshall(Graph &G) 調用最短路徑- - Floyd_Wallshall算法 參數:圖G*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<string>#include<set>#include<list>#include<queue>#include<vector>#include<map>#include<iterator>#include<algorithm>#include<iostream>#define MaxVerNum 100 //頂點最大數目值#define VexType char //頂點數據類型#define EdgeType int //弧數據類型,有向圖時鄰接矩陣不對稱,有權值時錶示權值,沒有時1連0不連#define INF 0x3f3f3f3f//作為最大值using namespace std;//圖的數據結構typedef struct Graph{ VexType Vex[MaxVerNum];//頂點錶 EdgeType Edge[MaxVerNum][MaxVerNum];//弧錶 int vexnum, arcnum;//頂點數、弧數}Graph;//迪傑斯特拉算法全局變量bool S[MaxVerNum]; //頂點集int D[MaxVerNum]; //到各個頂點的最短路徑int F_D[MaxVerNum][MaxVerNum];//Floyd的D矩陣 記錄最短路徑int Pr[MaxVerNum]; //記錄前驅//*********************************************基本操作函數*****************************************////初始化函數 參數:圖G 作用:初始化圖的頂點錶,鄰接矩陣等int P[MaxVerNum][MaxVerNum];//最短路徑記錄矩陣void InitGraph(Graph &G){ memset(G.Vex, '#', sizeof(G.Vex));//初始化頂點錶 //初始化弧錶 for (int i = 0; i < MaxVerNum; i++) for (int j = 0; j < MaxVerNum; j++) G.Edge[i][j] = INF; G.arcnum = G.vexnum = 0; //初始化頂點數、弧數}//插入點函數 參數:圖G,頂點v 作用:在圖G中插入頂點v,即改變頂點錶bool InsertNode(Graph &G, VexType v){ if (G.vexnum < MaxVerNum) { G.Vex[G.vexnum++] = v; return true; } return false;}//插入弧函數 參數:圖G,某弧兩端點v和w 作用:在圖G兩點v,w之間加入弧,即改變鄰接矩陣bool InsertEdge(Graph &G, VexType v, VexType w, int weight){ int p1, p2;//v,w兩點下標 p1 = p2 = -1;//初始化 for (int i = 0; i<G.vexnum; i++)//尋找頂點下標 { if (G.Vex[i] == v)p1 = i; if (G.Vex[i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//兩點均可在圖中找到 { G.Edge[p1][p2] = weight;//有向圖鄰接矩陣不對稱 G.arcnum++; return true; } return false;}//判斷是否存在弧(v,w)函數 參數:圖G,某弧兩端點v和w 作用:判斷是否存在弧(v,w) bool Adjancent(Graph G, VexType v, VexType w){ int p1, p2;//v,w兩點下標 p1 = p2 = -1;//初始化 for (int i = 0; i<G.vexnum; i++)//尋找頂點下標 { if (G.Vex[i] == v)p1 = i; if (G.Vex[i] == w)p2 = i; } if (-1 != p1&&-1 != p2)//兩點均可在圖中找到 { if (G.Edge[p1][p2] == 1)//存在弧 { return true; } return false; } return false;}bool visited[MaxVerNum];//訪問標記數組,用於遍曆時的標記//廣度遍曆函數 參數:圖G,開始結點下標start 作用:寬度遍曆void BFS(Graph G, int start){ queue<int> Q;//輔助隊列 cout << G.Vex[start];//訪問結點 visited[start] = true; Q.push(start);//入隊 while (!Q.empty())//隊列非空 { int v = Q.front();//得到隊頭元素 Q.pop();//出隊 for (int j = 0; j<G.vexnum; j++)//鄰接點 { if (G.Edge[v][j] < INF && !visited[j])//是鄰接點且未訪問 { cout << "->"; cout << G.Vex[j];//訪問結點 visited[j] = true; Q.push(j);//入隊 } } }//while cout << endl;}//深度遍曆函數(遞歸形式)參數:圖G,開始結點下標start 作用:深度遍曆void DFS(Graph G, int start){ cout << G.Vex[start];//訪問 visited[start] = true; for (int j = 0; j < G.vexnum; j++) { if (G.Edge[start][j] <INF && !visited[j])//是鄰接點且未訪問 { cout << "->"; DFS(G, j);//遞歸深度遍曆 } }}//最短路徑 - Dijkstra算法 參數:圖G、源點v3void Dijkstra(Graph G, int v){ //初始化 int n = G.vexnum;//n為圖的頂點個數 for (int i = 0; i < n; i++) { S[i] = false; D[i] = G.Edge[v][i]; if (D[i] < INF)Pr[i] = v; //v與i連接,v為前驅 else Pr[i] = -1; } S[v] = true; D[v] = 0; //初始化結束,求最短路徑,並加入S集 for (int i = 1; i < n; i++) { int min = INF; int temp; for (int w = 0; w < n; w++) if (!S[w] && D[w] < min) //某點temp未加入s集,且為當前最短路徑 { temp = w; min = D[w]; } S[temp] = true; //更新從源點出發至其餘點的最短路徑 通過temp for (int w = 0; w < n; w++) if (!S[w] && D[temp] + G.Edge[temp][w] < D[w]) { D[w] = D[temp] + G.Edge[temp][w]; Pr[w] = temp; } }}//最短路徑 - Bellman_Ford算法 參數:圖G、源點v 作用:計算不含負圈圖的最短路徑 返回是否有圈bool Bellman_Ford(Graph G, int v){ //初始化 int n = G.vexnum;//n為圖的頂點個數 for (int i = 0; i < n; i++) { D[i] = G.Edge[v][i]; if (D[i] < INF)Pr[i] = v; //v與i連接,v為前驅 else Pr[i] = -1; } D[v] = 0; //初始化結束,開始雙重循環 for (int i = 2; i<G.vexnum - 1; i++) for (int j = 0; j<G.vexnum; j++) //j為源點 for (int k = 0; k<G.vexnum; k++) //k為終點 if (D[k] > D[j] + G.Edge[j][k]) { D[k] = D[j] + G.Edge[j][k]; Pr[k] = j; } //判斷是否含有負圈 bool flag = true; for (int j = 0; j<G.vexnum - 1; j++) //j為源點 for (int k = 0; k<G.vexnum - 1; k++) //k為終點 if (D[k] > D[j] + G.Edge[j][k]) { flag = false; break; } return flag;}//最短路徑 - Floyd_Wallshall算法 參數:圖G 作用:計算不含負圈圖的最短路徑 返回是否有圈bool Floyd_Wallshall(Graph G){ //初始化 for (int i = 0; i<G.vexnum; i++) for (int j = 0; j < G.vexnum; j++) { if (i == j)F_D[i][j] = 0; else F_D[i][j] = G.Edge[i][j]; P[i][j] = -1; } //初始化結束,開始迭代 for(int k=0;k<G.vexnum;k++) for (int i = 0; i<G.vexnum; i++) for (int j = 0; j<G.vexnum; j++) if (F_D[i][j] > F_D[i][k] + F_D[k][j]) { F_D[i][j] = F_D[i][k] + F_D[k][j]; P[i][j] = k; } bool flag = true; for (int i = 0; i < G.vexnum; i++) for (int j = 0; j < G.vexnum; j++) if (i==j&&F_D[i][j] < 0) { flag = false; break; } return flag;}//輸出最短路徑void Path(Graph G, int v){ if (Pr[v] == -1) return; Path(G, Pr[v]); cout << G.Vex[Pr[v]] << "->";}// 輸出Floyd最短路徑 v是終點void F_Path(Graph G, int v, int w){ cout << "->"<< G.Vex[P[v][w]] ; if (P[v][w] == -1) return; F_Path(G, v,P[v][w]);}//**********************************************功能實現函數*****************************************////打印圖的頂點錶void PrintVex(Graph G){ for (int i = 0; i < G.vexnum; i++) { cout << G.Vex[i] << " "; } cout << endl;}//打印圖的弧矩陣void PrintEdge(Graph G){ for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (G.Edge[i][j] == INF)cout << "∞ "; else cout << G.Edge[i][j] << " "; } cout << endl; }}//創建圖功能實現函數 參數:圖G InsertNode 作用:創建圖void CreateGraph(Graph &G){ VexType v, w; int vn, an;//頂點數,弧數 cout << "請輸入頂點數目:" << endl; cin >> vn; cout << "請輸入弧數目:" << endl; cin >> an; cout << "請輸入所有頂點名稱:" << endl; for (int i = 0; i<vn; i++) { cin >> v; if (InsertNode(G, v)) continue;//插入點 else { cout << "輸入錯誤!" << endl; break; } } cout << "請輸入所有弧(每行輸入起點,終點及權值):" << endl; for (int j = 0; j<an; j++) { int weight; cin >> v >> w >> weight; if (InsertEdge(G, v, w, weight)) continue;//插入弧 else { cout << "輸入錯誤!" << endl; break; } } cout << "圖的頂點及鄰接矩陣:" << endl; PrintVex(G); PrintEdge(G);}//廣度遍曆功能實現函數 參數:圖G 作用:寬度遍曆void BFSTraverse(Graph G){ for (int i = 0; i<MaxVerNum; i++)//初始化訪問標記數組 { visited[i] = false; } for (int i = 0; i < G.vexnum; i++)//對每個連通分量進行遍曆 { if (!visited[i])BFS(G, i); }}//深度遍曆功能實現函數 參數:圖G 作用:深度遍曆void DFSTraverse(Graph G){ for (int i = 0; i<MaxVerNum; i++)//初始化訪問標記數組 { visited[i] = false; } for (int i = 0; i < G.vexnum; i++)//對每個連通分量進行遍曆 { if (!visited[i]) { DFS(G, i); cout << endl; } }}//調用最短路徑-Dijkstra算法 參數:圖Gvoid Shortest_Dijkstra(Graph &G){ char vname; int v = -1; cout << "請輸入源點名稱:" << endl; cin >> vname; for (int i = 0; i < G.vexnum; i++) if (G.Vex[i] == vname)v = i; if (v == -1) { cout << "沒有找到輸入點!" << endl; return; } Dijkstra(G, v); cout << "目標點" << "\t" << "最短路徑值" << "\t" << "最短路徑" << endl; for (int i = 0; i < G.vexnum; i++) { if (i != v) { cout << " " << G.Vex[i] << "\t" << " " << D[i] << "\t"; Path(G, i); cout << G.Vex[i] << endl; } }}//調用最短路徑- - Bellman_Ford算法 參數:圖Gvoid Shortest_Bellman_Ford(Graph &G){ char vname; int v = -1; cout << "請輸入源點名稱:" << endl; cin >> vname; for (int i = 0; i < G.vexnum; i++) if (G.Vex[i] == vname)v = i; if (v == -1) { cout << "沒有找到輸入點!" << endl; return; } if (Bellman_Ford(G, v)) { cout << "目標點" << "\t" << "最短路徑值" << "\t" << "最短路徑" << endl; for (int i = 0; i < G.vexnum; i++) { cout << " " << G.Vex[i] << "\t" << " " << D[i] << "\t"; Path(G, i); cout << G.Vex[i] << endl; } } else { cout << "輸入的圖中含有負圈,不能使用該算法!" << endl; }}//調用最短路徑- - Floyd_Wallshall算法 參數:圖Gvoid Shortest_Floyd_Wallshall(Graph &G){ if (Floyd_Wallshall(G)) { cout << "最短路徑值" << "\t" << "最短路徑" << endl; for (int i = 0; i < G.vexnum; i++) for (int j = 0; j < G.vexnum; j++) { cout << " "<<F_D[i][j] << " \t"; cout << G.Vex[i]; F_Path(G, i,j); cout << G.Vex[j] << endl; } } else { cout << "輸入的圖中含有負圈,不能使用該算法!" << endl; }}//菜單void menu(){ cout << "************1.創建圖 2.廣度遍曆******************" << endl; cout << "************3.深度遍曆 4.迪傑斯特拉****************" << endl; cout << "************5.貝爾曼福特 6.弗洛伊德******************" << endl; cout << "************7.退出*************************************" << endl;}//主函數int main(){ int choice = 0; Graph G; InitGraph(G); while (1) { menu(); printf("請輸入菜單序號:\n"); scanf("%d", &choice); if (7 == choice) break; switch (choice) { case 1:CreateGraph(G); break; case 2:BFSTraverse(G); break; case 3:DFSTraverse(G); break; case 4:Shortest_Dijkstra(G); break; case 5:Shortest_Bellman_Ford(G); break; case 6:Shortest_Floyd_Wallshall(G); break; default:printf("輸入錯誤!!!\n"); break; } } return 0;}

實驗結果

實驗結果截圖

最短路徑算法比較

算法\比較內容 適用條件 算法思想 時間複雜度
Dijkstra 無負權的圖,單源或多源 貪心 O(v^2)、O(v^3)
Bellman-Ford 可以有負權但無負圈的圖 動態規劃 O(v^3)、O(ve)
Floyd-Warshall 無負權的圖,多源 動態規劃

O(v^3)

版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201070809323980.html