Floyd算法（Floyd-Warshall算法）是一种用于求解所有顶点对之间最短路径的动态规划算法，适用于带权有向图或无向图（允许负权边，但不含负权环）。

---

优缺点及适用性

优点

1. 全局最优解
   直接计算出图中任意两个顶点之间的最短路径，而不仅针对单一源点。

2. 代码实现简单
   核心算法仅需三重循环，逻辑清晰（动态规划思想），易于编写。

3. 处理负权边
   允许图中存在负权边（只要没有负权环），而Dijkstra算法无法处理这种情况。

4. 无重复计算
   通过动态规划表（距离矩阵）逐步优化，避免重复计算子问题。

5. 适用于稠密图
   在稠密图（边数接近顶点数平方）中，性能可能优于多次调用Dijkstra或Bellman-Ford。

缺点

1. 时间复杂度高
   时间复杂度为 O(n3)（n为顶点数），在稀疏图或大规模图中效率较低。例如，对于1,000个顶点的图，需执行10亿次操作。

2. 空间复杂度高
   需维护 n×n 的距离矩阵，空间复杂度为 O(n2)，对内存消耗较大。

3. 无法处理负权环
   如果图中存在负权环，算法无法得到正确结果（但可检测出负权环的存在）。

4. 不适用动态图
   每次图结构变化（如增删边）时，需重新计算整个矩阵，无法高效增量更新。

5. 常数因子较大
   使理论复杂度与矩阵乘法相当，实际运行常数较大，对小规模图可能不如Dijkstra高效。

---

适用场景

• 小规模图（顶点数较少）或稠密图。

• 需要频繁查询任意两点间最短路径的场景。

• 图中存在负权边（但无负权环）。

---

总结

floyd算法编码简单（只需要三重for循环），但时间复杂度较大，无法处理大规模图。

---

使用方法

例如下图，我们有1～4四个顶点，不同顶点之间有不同的带权路径，现在要求解任意两个顶点之间的最短路径的权值。那么应该怎么做呢？

首先，我们可以将有向图转化为更加简便的表格，如下：

该表中每个点到其本身的距离为0，没有单向边直接连通的两个点之间距离为无穷大。

对于两个初始点之间的距离（1->2），如果存在第三个点（3）（中转点），使得这个中转点加进来之后，总距离变短了，那么我们可以知道这个中转点可以使两个初始点之间形成更短路径（1->3->2）。以此类推，如果存在第k个中转点，加进两个初始点之间，可以使总距离变短，那么第k个中转点可以使两个初始点之间形成更短路径（1->…->k->…->2）。当所有合法的中转点全部加到两个初始点之间后，所形成的路径便是最短路径。这个就是floyd算法的核心思路。

下面我们开始演示：

首先，我们先将所有顶点之间的距离存入一个二维数组e[i][j]。

之后，我们先将一号顶点作为中转点，如果其余两点间的距离比其中一点到1再到另一点的距离大，那么一号中转点的加入可以使两点之间的距离变短，我们就更新一下两点之间的数据。

代码如下：

for(int i=1;i<=n;i++)
{   
    for(int j=1;j<=n;j++)
        {
            if(e[i][j]>e[i][1]+e[1][j])
            {
                e[i][j]=e[i][1]+e[1][j];
            }
        }
}

更新之后的表格如下图所示：（绿色的表示更新后的距离）

以此类推，将二号点、三号点……k号点全部作为中转点循环一遍之后，我们就得出了任意两点之间的最短路径的权值，也就是最短距离。在后续的步骤中，我们通过访问e[i][j]的数据，即可得到任意两点之间的最短距离。

核心代码如下：

for(k=1;k<=n;k++)//依次经过1～n中的第k个点中转
{
    for(i=1;i<=n;i++)
    {
         for(j=1;j<=n;j++)
         {
            if(e[i][j]>e[i][k]+e[k][j];
            {
                e[i][j]=e[i][k]+e[k][j];
            }
         }   
    }
}