Floyd 学习笔记

最短路

性质

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。

对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过 $n$ ，边数不会超过 $n - 1$ 。

（以上引自OI-Wikii）

Floyd 算法

介绍

Floyd算法是用来求任意两个结点之间的最短路的。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ ，算法复杂度较高，不过常数较少，容易实现。

实现

定义一个数组 $\rm{f[k][x][y]}$ 表示只允许经过结点1到k，结点x到结点y的最短路长度。 $\rm{f[n][x][y]}$ 就是结点x到结点y的最短路径长度。我们对每一个结点思考另外两个结点目前的距离与经过这个节点后的距离哪个更近，如果加入这个结点后更近，则将两个结点的距离更新为加入这个结点之后的距离。则状态转移方程为：

$\rm{f[k][x][y] = min(\ f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]\ )}$

不过我们会很容易的发现，这个数组的第一维是没有用的，所以可以将方程改为：

$\rm{f[x][y] = min(\ f[x][y],f[x][k]+f[k][y]\ )}$

于是我们将空间复杂度从 $O(n^3)$ 优化到了 $O(n^2)$ 。

初始化：将 $\rm{f[i][i]}$ 初始化为0，将有边相连的两个结点之间的距离初始化为这条边的长度，将没有边相邻的两个结点的距离初始化为INF（虽然说为INF，不过在运算时可能会出现两个INF相加的情况，所以只需要初始化为一个远大于最大边权的值）。

for(int k = 1;k <= n;k++){
    for(int i = 1;i <= n;i++){
         for(int j = 1;j <= n;j++){
             f[i][j] = min( f[i][j], f[x][k] + f[k][y] );
         }
    }
}