floyd算法

Frenkie · 2019-10-25 18:53:10 · 个人记录

floyd算法常用来解决多源最短路问题，时间复杂度O(n^3),优点是代码量小，容易写，缺点是只能用邻接矩阵存边，空间复杂度较大，且时间复杂度也较大。

初始化：

int map[maxn][maxn]//邻接矩阵
......
memset(map,0x3f,sizeof(map));
for(int i=1;i<=n;i++)
  map[i][i]=0;

floyd:

for(int k=1;k<=n;k++)
  for(int i=1;i<=n;i++)
   for(int j=1;j<=n;j++)
     map[i][j]=max(map[i][j],map[i][k]+map[k][j]);