简单图论的知识

作者：菜鸟追梦旅行 | 2024-04-26 20:41:16

踩

简单图论的知识

文章目录

一、最短路径
二、最小生成树

一、最短路径

Floyd算法是一种求解多源最短路问题的算法。
在floyd中，图一般用邻接矩阵存储，边权可正可负，利用动态规划思想，逐步求解出任意两点之间的最短距离。
我们需要准备一个数组d[N][N][N]，初始化无穷。
d[k][i][j]表示路径(除去起点和终点)中编号最大的点编号<=k的情况下，点i到点j的最短距离。

//注意k作为中转点，必须放到最外层
for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
1
2
3
4
5

二、最小生成树

学习学习大佬

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/493008