《数据结构与算法》——Floyd算法总结

- 日理万妓 2021-12-03 12:53 471阅读 0赞

# 《数据结构与算法》——Floyd算法总结 #

在考研中，图的应用部分有四个大考点分别为**最小生成树**、**最短路径问题**、**拓扑排序**以及**关键路径**。在最短路径问题中有两个小考点分别为**Dijkstra****算法**和**Floyd****算法**。在本文，将对**Floyd**算法进行知识总结、讲解以及c++代码呈现。

目的

算法思想

手动实例

C++代码实现

参考文献

--------------------

## 目的 ##

为了求解一对顶点间的最短路径，我们可以用已知的Dijkstra算法，分别将两个顶点设置为起始点执行两次Dijkstra算法，然后从得出的dist和path数组中寻找相应值即可，若是求解所有顶点间的最短路径，则需要把每个顶点分别设置为起始点共执行|v|次Dijkstra算法，此时时间复杂度为o(|v|^3)。

为解决这个问题，弗洛伊德提出了另外一种算法，被称为Floyd算法。

## 算法思想 ##

设定存在|v|个顶点，分别编号1、2、3…n

1.设定矩阵dist\[0\]\[\]\[\]用来保存初始直接距离arcs\[\]\[\]，dist\[0\]\[i\]\[j\]表示第i个点到第j个点是否有直接连接，若有则将距离进行保存，若无联系则设置为INF(无穷大)。

2.试探地在ij两点之间添加k点，若加入k点之后距离i-k-j比直接到达的距离i-j要小，则将距离值进行更新保存，将所有的<i,j>顶点对全部进行试探加入k点计算得出的数据组成dist\[k\]\[\]\[\]数组，对k进行增长式遍历直至k = n结束最后一次试探加点。

3.此时得出了|v|个|v|\*|v|的矩阵，则此时在dist\[k\]\[i\]\[j\]中对于k从0到n进行遍历，选出最靠前的最小值即为i点到j点的最短距离，而此时在<i,…,j>路径中k即为j点的前驱节点，若为零，则无中间节点。如此计算可得出path数组，此处和Dijkstra算法相同。

## 手动实例 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70][]

教材191页图7.36 (a)

1.作出邻接矩阵

2.dists\[\]\[\]\[\]数组赋值，并开始计算。

3.选出最短路径，填写dist和path数组。

求解完毕。

## C++代码实现 ##

变量说明

dists\[\]\[\]\[\]：保存n个dist数组

dist\[\]\[\]：保存最终的最短路径

path\[\]：保存最终的最短路径的前驱节点。

/*编译环境：
 win10专业版
 DEV C++ 5.11
 TDM-GCC 4.9.2 64bit
 */
 #include<iostream>
 #define INF 65535
 #define Max 3
 #define v Max+1
 using namespace std;
 
 int dists[v][v][v];//记录过程矩阵 
 int dist[v][v];//记录最短路径 
 int path[v][v];//记录路径
 
 void Floyd(int G[][v],int n){
 		
 	//初始化dists
 	for(int i=1;i<=n;i++){
 		for(int j=1;j<=n;j++) 
 			dists[0][i][j] = G[i][j];
 		dists[0][0][i] = INF;
 		dists[0][i][0] = INF;
 	}
 		
 	
 	//核心部分 
 	for(int i=1;i<=n;i++) 
 		for(int j=1;j<=n;j++) 
 			for(int k=1;k<=n;k++)
 					dists[i][j][k] = (k==j)?0:(dists[i-1][j][k]>dists[i-1][j][i]+dists[i-1][i][k]?
 									 dists[i-1][j][i]+dists[i-1][i][k] : dists[i-1][j][k]);
 			/*	if(k==j)
 					dists[i][j][k] = 0;
 				else
 					dists[i][j][k] = dists[i-1][j][k]>dists[i-1][j][i]+dists[i-1][i][k]?dists[i-1][j][i]+dists[i-1][i][k] : dists[i-1][j][k];
 			*/
 			
 	//求dist和path
 	int temp;
 	int min; 
 	for(int i=1;i<=n;i++) 
 		for(int j=1;j<=n;j++)
 			if(i == j){
 				path[i][j] = -1;
 				dist[i][j] = 0;
 			}
 			else{
 				min = dists[0][i][j];
 				temp = i;//直接连接最近 
 				for(int k=1;k<=n;k++)//为了找出最小边 
 					if (dists[k][i][j] < min){
 						min = dists[k][i][j];
 						temp = k;
 					}
 				path[i][j] = temp;
 				dist[i][j] = min;	
 			}			
 }
 
 int main(){
 	int G[v][v];
 	int n = Max;
 	//需要对G初始化
 	G[1][1] = 0 ;
 	G[1][2] = 4 ;
 	G[1][3] = 11 ;
 	G[2][1] = 6 ;
 	G[2][2] = 0 ;
 	G[2][3] = 2 ;
 	G[3][1] = 3 ;
 	G[3][2] = INF ;
 	G[3][3] = 0 ;
 	Floyd(G,n);
 	//输出 
 	cout<<"初始G矩阵为："<<endl;	
 	for(int i=1;i<=n;i++) {
 		for(int j=1;j<=n;j++) 
 			cout<<G[i][j]<<"\t";
 		cout<<endl;
 	}
 	cout<<"\n******dists矩阵组******"<<endl;
 	for(int i=0;i<=n;i++) {
 	cout<<"\ndist["<<i-1<<"]矩阵为："<<endl;
 		for(int j=1;j<=n;j++) {
 			for(int k=1;k<=n;k++) 
 				cout<<dists[i][j][k]<<"\t";
 			cout<<endl;
 		}		
 	}
 	cout<<"\ndist矩阵为："<<endl;
 	for(int i=1;i<=n;i++) {
 		for(int j=1;j<=n;j++) 
 			cout<<dist[i][j]<<"\t";
 		cout<<endl;
 	}	
 	cout<<"\npath矩阵为："<<endl;
 	for(int i=1;i<=n;i++) {
 		for(int j=1;j<=n;j++) 
 			cout<<path[i][j]<<"\t";
 		cout<<endl;
 	}
 	return 0;
 }

## 参考文献 ##

严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.

王道论坛 2019年数据结构考研复习指导\[M\]. 北京： 电子工业出版社，2018.

如有错误，还请朋友不吝指正。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70]: /images/20211203/f09230a177fa4986a6a6b536e4e5f5db.png