今天我们老师讲了Floyd算法,使用想着总结一下,方便后面进行复习,使用如果在接下来的文章中有哪里写的不对,或者表达不恰当,欢迎提出,谢谢!
关于这个算法,我的理解是应用链接矩阵来进行存储值,通过比较来更新值,最后得出最短路径等问题的答案;
使用模板:
第一步就是使用宏定义来定义一个偏大的值,作为后面初始化的值,如:
#define inf 9999999
切记,后面不要加引号;
当然也可以这样来定义:
memset(Form, 0b00111111, sizeof(Form));
这里的From是数组名字;
需要取数组里面的值的话可以这样:
int x=Form[0][0];
随后定义一个链接矩阵,也就是一个二维数组,如:
int D[501][501];
根据题目的不同,对矩阵里面的值进行初始化;
如:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
D[i][j]=inf;
这里初始化时需要注意,题目提供的图是不是无向图,还是有向图;
从而对应初始化的值;
如无向图是这样的
for(int i=0;i<n;i++) for(int j=0;j<n;j++) D[i][j]=inf; for(int i=0;i<e;i++){ cin>>x>>y>>c; D[x][y]=c; D[y][x]=c; }
无向图在初始化时,每个坐标会分别对应两个值;
接下来就是以每个顶点作为中间点,来比较两边的路径相加是否比直通的路径权小,如果是比其小的话,更新值;
如:
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(D[i][j]>D[i][k]+D[k][j])
D[i][j]=D[i][k]+D[k][j];
好了,算法的表达部分就是到这里了,后面的内容就要看题目给的要求了;
例题详情见文章:最短路径算法(Floyd-Warshall) 及 双十一;
标签:初始化,Form,int,路径,算法,Floyd,模板 From: https://blog.csdn.net/wang3074162725/article/details/139144513