Flody
大家都知道这个最终模版:
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
那大家知道这个模版是怎么得出的吗?
核心思路:动态规划。
初始版本:
初始数组:dis(三维数组)
dis[i][j][k]表示i号到j号(只经过1~k号点)的路径
dis[i][j][0]=a[i][j](输入的数组)。
dis[i][j][n]表示从i到j可以经过n个点(其实就是怎么走都没问题)
dis[i][j][k-1]==>dis[i][j][k]
怎么通过一张初始的N*N的表得出最后的表?
dis[i][j][k]=?
i.....
.
.
j
如果不经过k号店,那么dis[i][j][k]=dis[i][j][k-1].
i....k
.
.
j
dis[i][j][k]=dis[i][j][k-1]+dis[k][j][k-1].
取最小值。
那么照着这个程序就是:
//两层循环省略
dis[i][j][0]=a[i][j]
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j][k]=min(dis[i][j][k-1],dia[i][k][k-1]+dis[k][j][k-1]);
第二版:
滚动数组
思路:
dis[*][*][k]=>dis1[*][*]
dis[*][*][k-1]=>dis0[*][*]
推倒这两个式子,可以得出滚动解法
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis1[i][j]=min(dis0[i][j],dis0[i][k]+dis0[k][j]);
dis0=dis1;//循环省略
}
实际上一直在优化空间
Flody算法更加适合稠密图,常用与多源最短路,求解稠密图于稀疏图时间一样。