floyd算法是多源最短路算法
也就是说,floyd可以一次跑出所以点两两之间的最短路
floyd类似动态规划
如下图:
用橙色表示边权,蓝色表示最短路
求最短路的流程是这样的:
先把点1到其他点的最短路求出
1 -> 2 的最短路是2
1 -> 3 的最短路可以由1 -> 2再由2 -> 3,2+5 = 7但1 -> 4再由4 -> 3更加短,所以1 -> 3的最短路为1+4 = 5
1 -> 4 的最短路是1
1 -> 5的最短路是3
2 也像这样求
我们发现,比如:
1到3可以由1到2再到3,或是1到4再到3
那我们可以枚举k,来看i先到k再到j的距离是否小于i到j的距离
然后可以列出状态转移方程:
dis[i][j]=min{dis[i][k]+dis[k][j]} (i≠j≠k)
其中dis[i][j]表示i到j的距离
代码如下:
void floyd() { for (int k = 1;k <= n;k++) for (int i = 1;i <= n;i++) for (int j = 1;j <= n;i++) dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]); }