算法基础篇（11）Floyd算法

Floyd算法本质是动态规划，用来求任意两点之间的最短路，也称为插点法。通过不断在两点之间加入新的点来更新最短路。

1、状态表示：f[k][i][j]表示：仅仅经过1~k这些点，结点i走到结点j的最短路径的长度。

2、状态转移方程：

情况1：不选新来的点：f[k][i][j] = f[k - 1][i][j]

情况2：选择新来的点：f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j]

3、空间优化：只会用到上一层的状态，因此可以优化掉第一维

4、初始化：按照邻接矩阵的方式初始化

5、填表顺序：先枚举k，再枚举i，j

流程图如下：