1. 定义

Floyd算法是一种用于寻找给定的加权图中顶点间最短路径，是经典的多源最短路径算法，可以有效地处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyd算法的时间复杂度为 O($N^3$)，空间复杂度为 O($N^2$)。

2. 优缺点

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单，适合于求任意两点的最短距离。

缺点：时间复杂度比较高，不是和计算大量数据。

3. 基本思想

Floyd 算法属于动态规划算法，即寻找节点 $i$ 到节点 $j$ 的最短路径。

3.1 初始距离

定义 $n$ 节点网络的邻接矩阵 A($n×n$) ，矩阵中的元素为 $a_{(i,j)}$ 为节点 $i$ 到节点 $j$ 的一步的直线距离。初始矩阵元素为的规则为：

1. $i$, $j$ 相连: $a_{i,j}$=$c_{(i,j)}$

2. $i$ 等于 $j$：$a_{i,j}=0$

3. $i$, $j$ 不相连：$\infty$

如下图：

则该初始邻接矩阵 A 为：

即节点 0 与节点 0 自身距离值为0，即 A[0][0]=0 ；节点0与节点1之间有直线连接，距离值为5，即 A[0][1]=5;

节点 0 与节点 2 之间没有直线连接，则距离值为 $\infty$，即 A[0][2] = $\infty$；

节点 0 与节点3之间有直线连接，距离值为 7，即 A[0][3]=7

……

其他节点间的初始距离可依次写出，即为该邻接矩阵 A 。

3.2: 矩阵迭代，找最短路径

对矩阵做 n 次迭代。每一轮迭代，就是枚举一个插入点 $k$，假设之前 $i$ 点和 $j$ 点经过 $k$ 的跳转能实现更短的距离，则对边 e(i,j) 进行松弛。

我们定义一个三维数组数组: dp[x][i][j] ，第一维度 $x$ 表示在考虑了 $1 \dot x$ 这若干个点，$i$ 表示出点作为中间插入点，$j$ 表示点，数组里记录的是最短距离。例如 dp[0][1][3] 记录的是没有任何插入点的情况下，从顶点 1 到顶点 3 的距离；而 dp[1][2][4] 记录的是考虑了把顶点 1 作为插入点之后，顶点 2 到顶点 4 的最短距离，我们很容易知道考虑了顶点 1 作为插入点，那就多了一条路径： 2->1->4 ，所以 dp[1][2][4] = min(dp[0][2][4], dp[0][2][1]+dp[0][1][4])，$这个式子进一步推广，就是 dp[x][i][j] = min(dp[x-1][i][j], dp[x-1][i][?]+dp[x-1][?][j]) ，式子当中的 ？ 应该是对所有点的枚举。这个思想在程序上体现为：

for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
            dp[0][i][j] = a[i][j]; // 第一维为 0 的时候，就是没有任何插入点，两点的距离取自邻接矩阵的边长。

for(int i=1;i<=n;i<=n){ // 第 i 轮松弛操作，基于第 i-1 轮的松弛结果 dp[i-1][][]
      for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                  dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j][i] + dp[i-1][i][k]);
                  // 第 i 轮的松弛操作，是在所有点对之间试图插入顶点 i， 所以，j->k 的尝试被 j->i->k 松弛
            }
      }
}

上面这个代码是方便大家理解的，松弛操作的时候，dp[i][j][k] 要么等于 dp[i-1][j][k]，要么等于 dp[i-1][j][i] + dp[i-1][i][k]，可以用自我迭代的方式去掉第一维，直接基于邻接矩阵进行运算，然后程序就可以写成下面这样。

1: for(int i=1;i<=n;i<=n) // 第 i 轮松弛操作，基于第 i-1 轮的松弛结果 dp[i-1][][]
2:       for(int j=1;j<=n;j++)
3:            for(int k=1;k<=n;k++)
4:                  a[j][k] = min(a[j][k], a[j][i]+a[i][k]);

上述代码中，很重要的几点：

1. 要搞清楚 3 层循环代表的是什么，i 代表的是尝试插入的点，j 代表的是出点，k 代表的是入点。如果这三层循环代表什么不清楚，这个程序就没办法写得对

2. 第一层循环 i 是很重要的。i 循环到 5 的时候，还没执行到第 4 行的时候，a[j][k] 的路径值是没有考虑经过顶点 5 的，只有执行完第 4 行，a[j][k] 里面才算是把顶点 5 考虑进去。考虑进去不是说就一定包含顶点 5 ，而是说如果经过顶点 5 会走了一条捷径的话就会走顶点 5 ，如果没有捷径，那即便考虑完，也不会包含顶点 5 。

3. 上述代码是同时适用于有向图和无向图的。在无向图中 ,a[i][j] = a[j][i]，而对于有向图，一条边是单向的，即便存在顶点 i 到 j 的边，但未必存在 j 到 i 的边（反向），即便存在，边权也可以不一样。如果对于无向图，上述的代码可以简化为：

1: for(int i=1;i<=n;i<=n) // 第 i 轮松弛操作，基于第 i-1 轮的松弛结果 dp[i-1][][]
2:       for(int j=1;j<=n;j++)
3:            for(int k=j+1;k<=n;k++) // 只需要枚举一半的邻接矩阵
4:                  a[k][j] = a[j][k] = min(a[j][k], a[j][i]+a[i][k]); // 无向图，a[k][j] = a[j][k]

4. floyd 算法的代码比较简单，比较好理解，但是时间复杂度很高。很多题目只让你求两点之间的最短距离，floyd 算出的是所有点对之间的最短距离，类似用大炮打蚊子，很容易造成超时。