南京产品网站建设收费,seo网站优化软件,jquery验证网站地址,北京西城区建设局网站一.简介 Floyd算法#xff0c;也称为Floyd-Warshall算法#xff0c;是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。
Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两…一.简介 Floyd算法也称为Floyd-Warshall算法是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。
Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两个节点之间的最短路径长度并通过不断更新这个数组来得到最终的结果。
算法的步骤如下
初始化一个二维数组用于存储节点之间的最短路径长度。将数组的初始值设置为图中节点之间的直接距离如果两个节点之间没有直接连接则距离为无穷大。对于每个节点k遍历所有节点对(i, j)并尝试通过节点k来优化路径长度。如果通过节点k可以获得更短的路径则更新数组中的值。重复步骤3直到所有节点对的最短路径长度都被计算出来。
Floyd算法的时间复杂度为O(n^3)其中n是图中节点的数量。它适用于解决稠密图边数接近节点数的平方的最短路径问题但对于稀疏图来说可能存在更高效的算法。
总的来说Floyd算法是一种非常经典且实用的算法可以在有向图或带权图中找到任意两个节点之间的最短路径。 二.存图方法
因为是解决多源最短路所以使用邻接矩阵存图。 三.原理
逐渐利用每个点进行搭桥实现中转功能。过程中带有dp的思想因为要使用搭完桥之后的最短路径进行再次搭桥从而实现最优解。 四.核心代码
for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)g[i][j]min(g[i][j],g[i][k]g[k][j]); 五.很重要的一道题
P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 六.此题好的原因
考察了对选手floyd算法的进一步理解而不是单纯的背板子 七.难点
最短路径是很好求的但题目要求的时间是个大难题。有些路在一个时间点并不能用更不能起到搭桥作用。所以输出答案时并不能只考虑起点和终点不能走还有考虑不能走对其他点最短路的影响。 八.解决方案
既然没到时间就不能用这个点搭桥那我们在计算整体最短路时不用不就行了吗在floyd算法中第一重遍历中的k就是用这个点进行搭桥那我们就没到时间这前就不遍历即可。 九.参考代码
#includeiostream
#includecstdio
#define N 205
using namespace std;
int n,m;
int a[N];
int f[N][N];//邻接矩阵存边
inline void updata(int k){for(int i0;in;i)for(int j0;jn;j)if(f[i][j]f[i][k]f[j][k])f[i][j]f[j][i]f[i][k]f[j][k];//用这个新的更新所有前面的 return;
}
int main(){cinnm;for(int i0;in;i)scanf(%d,a[i]);//依次输入每一个村庄建立完成时需要的时间for(int i0;in;i)for(int j0;jn;j){f[i][j]1e9;//初始化为保证它不爆炸范围内的最大值 }for(int i0;in;i)f[i][i]0;int s1,s2,s3;for(int i1;im;i){scanf(%d%d%d,s1,s2,s3);f[s1][s2]f[s2][s1]s3;//初始化边长 }int q;cinq;int now0;for(int i1;iq;i){//处理各询问 scanf(%d%d%d,s1,s2,s3); //s3为可用时间点 s1为x点s2为y点 while(a[now]s3nown){updata(now);//依次更新点使它可以被用来更新其他的点 now;}if(a[s1]s3||a[s2]s3)cout-1endl;else {if(f[s1][s2]1e9)cout-1endl;else coutf[s1][s2]endl;}}return 0;
}
