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再枚举ij流程图如下
算法基础篇（11）Floyd算法
发布时间：2026/5/19 23:48:11
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再枚举ij流程图如下
