弗洛伊德(Floyd)

今天520 没错我还在这写代码
我的座右铭“心中无女人 拔剑自然神 剑谱第一式，忘掉心上人”
但是今天这里同样送给大家一个表白语录
思念一个人的极致是什么——只要岁岁平安，即使，生生不见

文章目录

• 前言
• 基本原理(重要)
• 运行截图
• 代码汇总

---

前言

与前面的贝尔曼福特，迪杰斯特拉不同的是 这里计算任意两个结点之间的最短之间的最短路径 因为这个其实也是动态规划，也是有难度的，本来图这个章节就应该再写完动态规划，贪心，递归什么的再来写的 但是 这样那样写的话 我觉得会有许多人看不懂，当然也包括我 这里主要写怎么给算法写出来。

基本原理(重要)

弗洛伊德算法是基于动态规划算法实现的。是一种求取图中任意两点间最短路径的算法。如果我们要求取S到E的最短路径，若这条最短路径会经过A点，那么就必然有下面这个不等式成立SA+AE<=SE 基于这个等式 只要我们找到了最短路径会经过的所有的点 那么我们也就找到了这个路径 希望将加粗的字体读三遍
大家应该也知道实现主要就是三个循环，内层的两个循环其实就是指的是任意的两个点i,j 最外层的则是两个点之间的第三个点k(尽管有的点并不经过) 三层for 实质就是上述黑体字的实现,我们就是在循环之中不断比较从i到j的距离与从i到k距离加上从k到j距离的大小，如果经过这个点，路径变短了，我们就接受这个点，认为可以经过这个点；否则就不经过这个点，就是从i到j最短。(简单来说就是若是通过路k绕一下更短，那就绕路)所以这里使用还要使用另外一个矩阵来存储两个点之间要经过的点，记住存储的是结点！结点！ 结点！那么通过存储的结点怎么就知道路径呢？比如我们i j 中存储的就是k 那么我们通过找到的k 是不是i k 也存储着一个点，最后也就知道了起始结点，最后逆向输出就是正向的路径

上面的文字是重点 建议认真阅读
基于上述我们其实就可以写出代码了，

void Floyd(AMGraph &G){ 
	int dict[G.vexnum][G.vexnum];//用来存储点与点之间之间的距离
	char path[G.vexnum][G.vexnum];//用来存储点与点之间的中中介 
	//因为之前若是没有边 放的是0  这里将0 修改成MaxInt 
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			path[i][j]='N';
			if(i!=j&&0==G.arcs[i][j]){
				G.arcs[i][j]=MaxInt;
			}
			dict[i][j]=G.arcs[i][j];//路径初始化  
		}
	}
	cout<<"初始化的dict数组是"<<endl; 
	cout<<"顶点"<<"\t";
	for(int i=0;i<G.vexnum;i++) cout<<G.vexs[i]<<"\t";
	cout<<endl; 
	for(int i=0;i<G.vexnum;i++){ 
		cout<<G.vexs[i]<<"\t"; 
		for(int j=0;j<G.vexnum;j++){
			cout<<dict[i][j]<<"\t"; 
		}
		cout<<endl;
	}
	cout<<endl; 
	for(int k=0;k<G.vexnum;k++){
		//遍历每一个点，判断该点k加入到ij之中是否会让边ij变短 
		for(int i=0;i<G.vexnum;i++){ 
			for(int j=0;j<G.vexnum;j++){
				if (dict[i][k]!=MaxInt&&dict[k][j]!=MaxInt&&dict[i][k]+dict[k][j]<dict[i][j]){
					dict[i][j]=dict[i][k]+dict[k][j];
					path[i][j]=G.vexs[k];
				}
			}
		}
	}
	cout<<"此时的dict数组是"<<endl; 
	cout<<"顶点"<<"\t";
	for(int i=0;i<G.vexnum;i++) cout<<G.vexs[i]<<"\t";
	cout<<endl; 
	for(int i=0;i<G.vexnum;i++){ 
		cout<<G.vexs[i]<<"\t"; 
		for(int j=0;j<G.vexnum;j++){
			cout<<dict[i][j]<<"\t"; 
		}
		cout<<endl;
	}
	cout<<endl; 
	cout<<"此时的路径数组是"<<endl; 
	cout<<"顶点"<<"\t";
	for(int i=0;i<G.vexnum;i++) cout<<G.vexs[i]<<"\t";
	cout<<endl; 
	for(int i=0;i<G.vexnum;i++){ 
		cout<<G.vexs[i]<<"\t"; 
		for(int j=0;j<G.vexnum;j++){
			cout<<path[i][j]<<"\t"; 
		}
		cout<<endl;
	}
	cout<<endl; 
}

运行截图

测试用图

32767 表示不可达 路径数组中N 表示不可达，或点i j 直接相连 并不经过中间结点 以及对角线时候

这里个人认为需要加上一个if (dict[i][k]!=MaxInt&&dict[k][j]!=MaxInt&&dict[i][k]+dict[k][j] 若是不加 运行结果 同样的图 BE 之间居然有点了 大家可以上机 *** 作一下 后面有可执行

毕竟是经典的算法 ，贸然的挑战他 可能是我的理解不对，若是理解有误，希望大家指正

代码汇总

#include
using namespace std;
#define MaxInt 32767  //表示极大值∞  其实就是一种无穷标志
#define MVNum  100    //表示最大顶点数 
typedef char VerTexType;//假设顶点的数据结构类型为char 
typedef int  ArcType;//假设权值类型为整形
//下面的是邻接矩阵的 
typedef struct{
	 VerTexType vexs[MVNum];//顶点表 
	 ArcType  arcs[MVNum][MVNum];//邻接矩阵 
	 int vexnum;//图的当前顶点数
	 int arcnum;//图的当前边数
}AMGraph;
//打印邻接矩阵 
void PrintAMG(AMGraph G){
	cout<<" "<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" "; 
		for(int j=0;j<G.vexnum;j++){
			cout<<G.arcs[i][j]<<" ";
		}
		cout<<endl;
	}
} 
//创建一个无向图 ，其实就是填充两个数组 
void CreateAdjoin(AMGraph &G){
	cout<<"请输入顶点数和边数"<<endl;
	cin>>G.vexnum>>G.arcnum; 
	cout<<"请输入各个顶点名称"<<endl; 
	for(int i=0;i<G.vexnum;i++){
		cin>>G.vexs[i]; 
	}
	for(int h=0;h<G.arcnum;h++){
		char vex1;char vex2;
		cout<<"请输入弧的两个顶点"<<endl;
		cin>>vex1>>vex2; 
		//首先来看是否存在这两个顶点  若是存在则找到这两个点对应的下标
		// 当然创建的时候一种更加简单的方式就是遍历二维数组 一个一个输入
		int i=0;while(G.vexs[i++]!=vex1);
		int j=0;while(G.vexs[j++]!=vex2);
		if(i>G.vexnum||j>G.vexnum){//没有找到 
			cout<<"你输入的结点值不正确"<<endl; 
		}
		else{
			cout<<"请输入此边对应的权重"<<endl; 
			cin>>G.arcs[i-1][j-1];
			//G.arcs[j-1][i-1]=G.arcs[i-1][j-1];
		}
	}
	PrintAMG(G);
}
/**/ 
void Floyd(AMGraph &G){ 
	int dict[G.vexnum][G.vexnum];//用来存储点与点之间之间的距离
	char path[G.vexnum][G.vexnum];//用来存储点与点之间的中中介 
	//因为之前若是没有边 放的是0  这里将0 修改成MaxInt 
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			path[i][j]='N';
			if(i!=j&&0==G.arcs[i][j]){
				G.arcs[i][j]=MaxInt;
			}
			dict[i][j]=G.arcs[i][j];//路径初始化  
		}
	}
	cout<<"初始化的dict数组是"<<endl; 
	cout<<"顶点"<<"\t";
	for(int i=0;i<G.vexnum;i++) cout<<G.vexs[i]<<"\t";
	cout<<endl; 
	for(int i=0;i<G.vexnum;i++){ 
		cout<<G.vexs[i]<<"\t"; 
		for(int j=0;j<G.vexnum;j++){
			cout<<dict[i][j]<<"\t"; 
		}
		cout<<endl;
	}
	cout<<endl; 
	for(int k=0;k<G.vexnum;k++){
		//遍历每一个点，判断该点k加入到ij之中是否会让边ij变短 
		for(int i=0;i<G.vexnum;i++){ 
			for(int j=0;j<G.vexnum;j++){
				if (dict[i][k]+dict[k][j]<dict[i][j]){
					dict[i][j]=dict[i][k]+dict[k][j];
					path[i][j]=G.vexs[k];
				}
			}
		}
	}
	cout<<"此时的dict数组是"<<endl; 
	cout<<"顶点"<<"\t";
	for(int i=0;i<G.vexnum;i++) cout<<G.vexs[i]<<"\t";
	cout<<endl; 
	for(int i=0;i<G.vexnum;i++){ 
		cout<<G.vexs[i]<<"\t"; 
		for(int j=0;j<G.vexnum;j++){
			cout<<dict[i][j]<<"\t"; 
		}
		cout<<endl;
	}
	cout<<endl; 
	cout<<"此时的路径数组是"<<endl; 
	cout<<"顶点"<<"\t";
	for(int i=0;i<G.vexnum;i++) cout<<G.vexs[i]<<"\t";
	cout<<endl; 
	for(int i=0;i<G.vexnum;i++){ 
		cout<<G.vexs[i]<<"\t"; 
		for(int j=0;j<G.vexnum;j++){
			cout<<path[i][j]<<"\t"; 
		}
		cout<<endl;
	}
	cout<<endl; 
}
int main(){
	AMGraph G;
	CreateAdjoin(G);
	Floyd(G); 
}

感觉不错点个赞吧 爱你