Floyd算法

Floyd-Warshall概念

Floyd-Warshall算法是一种经典的图算法，用于求解图中所有顶点对之间的最短路径（多源最短路）。该算法适用于有向图或无向图，可以处理带有负权边（但不能存在负权回路）的图。Floyd-Warshall算法的主要思想是动态规划，通过逐步更新所有顶点对之间的最短路径信息来求解问题。

算法步骤：

初始化：将图的邻接矩阵表示的路径权值矩阵初始化为图中的边权值。如果不存在边，则权值设为无穷大（表示不可达），对角线元素初始化为0。

动态规划：对于每一对顶点（i，j），以每个顶点k为中间节点，尝试更新从i到j的最短路径。如果通过中间节点k的路径比直接路径更短，则更新路径。

迭代更新：重复上述动态规划步骤，对每一对顶点都进行动态规划，直到所有顶点对之间的最短路径都得到了更新。

简述

Floyd算法是一个暴力并且美丽的算法，算法一共三重循环，分别枚举三个点。

• 断点
• 出发点
• 终点

状态表示 d[k,i,j] 所有从i出发，最终走到j，且中间只经过节点编号不超过k的所有路径
分成两部分:

• d[k-1][i][j] 所有不含k的路径
• d[k-1][i][k] + d[k-1][k][j] 所有包含k的路径
  观察发现，我们可以优化掉第一维

状态转移方程也非常好记:
$$
d[i][j] = min(d[i][j],d[i][k] + d[k][j])
$$

正确性证明

来自大佬的证明

算法模板

//初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}