Floyd算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Floyd算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1419字，纯文字阅读大概需要3分钟。

内容图文

上图中有 4 个城市 8 条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。

当任意两点之间不允许经过第三个点时，这些城市之间最短路程就是初始路程，如下。

在只允许经过 1 号顶点的情况下，任意两点之间的最短路程更新为：

在只允许经过 1 和 2 号顶点的情况下，任意两点之间的最短路程更新为：

同理，继续在只允许经过 1、2 和 3 号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为：

最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为：

核心代码

	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(e[i][j]>e[i][k]+e[k][j])
				e[i][j]=e[i][k]+e[k][j];

基本思想：最开始只允许经过 1 号顶点进行中转，接下来只允许经过 1 和 2 号顶点进行中转……允许经过 1~n 号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从 i 号顶点到 j 号顶点只经过前k号点的最短路程。
下面给出这个算法的完整代码：

#include<iostream>
using namespace std;
int main()
{
	int e[101][101];
	int n,m;
	int a,b,c;
	cin>>n>>m;
	//数组初始化 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)
				e[i][j]=0;
			else
				e[i][j]=99999999;
		}
	}
	//初始化各顶点之间的权值 
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		e[a][b]=c;
	}
	//核心算法 
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(e[i][j]>e[i][k]+e[k][j])
				e[i][j]=e[i][k]+e[k][j];
				
	cout<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<e[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

任意两点之间最终的最短路程如下：

内容总结

以上是互联网集市为您收集整理的Floyd算法全部内容，希望文章能够帮你解决Floyd算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---