【图论】Floyd算法(求2点间最短路径)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【图论】Floyd算法(求2点间最短路径)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含862字，纯文字阅读大概需要2分钟。

内容图文

来道例题吧：hdu1874

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f

const int maxn=205;
int n,m;
int mp[maxn][maxn];

int main(){
	while(cin>>n>>m){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==j) mp[i][j]=0;
				else mp[i][j]=INF;
			}
		}

		for(int i=1;i<=m;i++){
			int x,y,z;cin>>x>>y>>z;
			mp[x][y]=min(z,mp[x][y]);
			mp[y][x]=min(z,mp[y][x]);
		}
		
		int s,t;cin>>s>>t;
		//Floyd的写法：
		for(int k=0;k<n;k++){
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
				}
			}
		}
		//止
		if(mp[s][t]==INF) cout<<"-1"<<endl;
		else cout<<mp[s][t]<<endl;
	}
}

这里我解释一下Floyd算法，他是求两个点最短路径的，这里运用了dp的思维。
设起点为s，终点为t，路过的一个点(即搭桥点为k)
核心关键就是dp[s][t]=min(dp[s][t],dp[s][k]+dp[k][t])
这就是状态转移，最后存最小即可

• 点赞
• 收藏
• 分享
• • 文章举报

Anonytt_ 发布了71 篇原创文章 · 获赞 5 · 访问量 3384 私信 关注

内容总结

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

内容备注

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

内容手机端

---