Floyd 算法（全称 Floyd–Warshall 算法）是一种用来求多源最短路径即所有点对之间的最短路径（APSP）的动态规划算法。该算法的核心思想很简单，就一句话：

通过动态规划，枚举所有中间节点，逐步更新任意两点之间的最短路径。

状态转移

既然是动态规划，那么必然会有状态转移定义，Floyd算法的状态转移在代码中是这样实现的：

dist[i][j] = min(
    dist[i][j],
    dist[i][k] + dist[k][j]
)

其中k为图中的任意节点，整个状态转移方程的含义是：

从顶点i到顶点j的最短路径，要么不经过顶点 k，保留原值 dist[i][j]；要么经过顶点 k，走 i→k→j这条路径。在这两者中取最小值，就是当前阶段的最优解。

从动态规划的角度严格描述为：

dp_{k}(i,j)=min(dp_{k-1}(i,j),dp_{k-1}(i,k)+dp_{k-1}(k,j))

Dijkstra Vs Floyd

        看到这儿，可能有人感觉这和 Dijkstra 算法的“松弛操作”（不断加入新结点、更新 dist数组）有些类似，但实际上二者思想完全不同：

  • Dijkstra 是贪心 + 单源：

    每次从当前未确定最短路径的顶点集合中，选出距离源点最近的顶点，并以它为中继去“松弛”其他顶点。它依赖于非负权值，一旦某个顶点被确定为最短路径，就不再参与后续更新。

  • Floyd 是动态规划 + 多源：

    不区分源点和终点，而是分阶段地引入“允许使用的中间点”。

    每一次循环都是在回答这样一个子问题：

    “如果只允许使用顶点 {1…k}作为中转，此时 i→j的最短路径是多少？”

    随着 k的增加，子问题的解逐渐逼近全局最优解。

一句话总结两者的区别：

Dijkstra是在“选下一个最近的顶点”。

Floyd 是在“允许更多的中转点”。

代码实现

        Floyd算法的实现其实非常简单，就三层for循环就可以搞定，最外层是关于k的循环，表示当前允许使用的转移点集合(范围是图中所有顶点)，内层则是枚举图中所有的起点 i和终点 j，在全图范围内统一做一次状态转移。

for k in range(n):#逐步放开中间点
    for i in range(n): #枚举起点
        for j in range(n):#枚举终点
            dist[i][j] = min(dist[i][j],
                             dist[i][k] + dist[k][j])

中转说明

        Floyd算法中，图的存储结构必须是领接矩阵，因为只有领接矩阵才方便实现状态转移的定义。实际上，在图中凡是“点到点”的算法，都适合使用邻接矩阵，凡是“边驱动”的算法，适合使用领接表。

        还需要注意的是：

  • 在代码的外层每一轮循环结束后，此时的矩阵使用A^{k}来表示(图中的顶点从1开始编号时，A^{0}表示原领接矩阵，图中的顶点从0开始编号时，A^{-1}表示原领接矩阵)。
  • 在第k轮时，A[k][j],j\in\left \{ 1,n \right \}，第K行没必要更新”或“更新无效果。
  • 无论是那一轮，主对角线上的点A[i][i]都是0，当然这个也有局限(图中不存在自环-自己指向自己的路径)，绝大多数题目无论是考研真题还是期末考试题这个都不会设计。
  • 实际做题，节点中转更新路径时，建议按行扫描来更新(原因如上一点所说)。

例题

例子是最好的学习工具，来做一道题加深一下印象。

        题目要求求解每次迭代过程中求得的最短路径长度，其实就是让我们将代码最外层循环，k=1,2,3...时每一轮的结果记录下来。

for k in range(n):#逐步放开中间点
    for i in range(n): #枚举起点
        for j in range(n):#枚举终点
            dist[i][j] = min(dist[i][j],
                             dist[i][k] + dist[k][j])

K=1

       k=1时，允许使用顶点1中转，那我们就需要在矩阵中遍历每一个值并按照下式比较大小，将二者中更小的那一个作为dist[i][j]当前路径的最小值。

#dist[i][1]+dist[1][j]就表示通过顶点1中转
dist[i][j]=min(dist[i][j],dist[i][1]+dist[1][j])
A^{0}(原始邻接矩阵)
0 10 ∞ 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0

前边说到，在算法执行过程中A[k][j]这一行更新无效果，本轮K=1，故直接从第二行开始更新。

在原始邻接矩阵第二行中,挨个查找比较，计算与比较结果若下表所示：

第二行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[2][1] ∞ A[2][1]+A[1][1]=∞+0 ∞ ∞
A[2][2] 0 A[2][1]+A[1][2]=∞+10 ∞ 0
A[2][3] ∞ A[2][1]+A[1][3]=∞+∞ ∞ 50
A[2][4] ∞ A[2][1]+A[1][4]=∞+30 ∞ ∞
A[2][5] ∞ A[2][1]+A[1][5]=∞+100 ∞ ∞

在原始邻接矩阵第三行中，挨个查找比较，计算与比较结果如下表所示：

第三行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[3][1] ∞ A[3][1]+A[1][1]=∞+0 ∞ ∞
A[3][2] ∞ A[3[1]+A[1][2]=∞+10 ∞ ∞
A[3][3] 0 A[3][1]+A[1][3]=∞+∞ ∞ 0
A[3][4] ∞ A[3][1]+A[1][4]=∞+30 ∞ ∞
A[3][5] 10 A[3][1]+A[1][5]=∞+100 ∞ 10

在原始邻接矩阵第四行中，挨个查找比较，计算与比较结果如下表所示：

第四行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[4][1] ∞ A[4][1]+A[1][1]=∞+0 ∞ ∞
A[4][2] ∞ A[4][1]+A[1][2]=∞+10 ∞ ∞
A[4][3] 20 A[4][1]+A[1][3]=∞+∞ ∞ 20
A[4][4] 0 A[4][1]+A[1][4]=∞+30 ∞ 0
A[4][5] 60 A[4][1]+A[1][5]=∞+100 ∞ 60

在原始邻接矩阵第五行中，挨个查找比较，计算与比较结果如下表所示：

第五行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[5][1] ∞ A[5][1]+A[1][1]=∞+0 ∞ ∞
A[5][2] ∞ A[5][1]+A[1][2]=∞+10 ∞ ∞
A[5][3] ∞ A[5][1]+A[1][3]=∞+∞ ∞ ∞
A[5][4] ∞ A[5][1]+A[1][4]=∞+30 ∞ ∞
A[5][5] 0 A[5][1]+A[1][5]=∞+100 ∞ 0

整理每个表格中最后一列选择的实际路径，可以得到算法第一轮结果，即A^{1}

A1
0 10 ∞ 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0

可以发现，没有什么变化。。。

K=2

          k=2时，允许使用顶点2中转(在A^{1}的基础上)，那我们就需要在矩阵中遍历每一个值并按照下式比较大小，将二者中更小的那一个作为dist[i][j]当前路径的最小值。

#dist[i][2]+dist[2][j]就表示通过顶点2中转
dist[i][j]=min(dist[i][j],dist[i][2]+dist[2][j])
A^{1}(上一轮邻接矩阵)
0 10 ∞ 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0

在原始邻接矩阵第一行中,挨个查找比较，计算与比较结果若下表所示：

第一行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[1][1] 0 A[1][2]+A[2][1]=10+∞ ∞ 0
A[1][2] 10 A[1][2]+A[2][2]=10+0 10 10
A[1][3] ∞ A[1][2]+A[2][3]=10+50 60 60
A[1][4] 30 A[1][2]+A[2][4]=10+∞ ∞ 30
A[1][5] 100 A[1][2]+A[2][5]=10+∞ ∞ 100

在原始邻接矩阵第三行中，挨个查找比较，计算与比较结果如下表所示：

第三行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[3][1] ∞ A[3][2]+A[2][1]=∞+∞ ∞ ∞
A[3][2] ∞ A[3[2]+A[2][2]=∞+0 ∞ ∞
A[3][3] 0 A[3][2]+A[2][3]=∞+50 ∞ 0
A[3][4] ∞ A[3][2]+A[2][4]=∞+∞ ∞ ∞
A[3][5] 10 A[3][2]+A[2][5]=∞+∞ ∞ 10

在原始邻接矩阵第四行中，挨个查找比较，计算与比较结果如下表所示：

第四行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[4][1] ∞ A[4][2]+A[2][1]=∞+∞ ∞ ∞
A[4][2] ∞ A[4][2]+A[2][2]=∞+0 ∞ ∞
A[4][3] 20 A[4][2]+A[2][3]=∞+50 ∞ 20
A[4][4] 0 A[4][2]+A[2][4]=∞+∞ ∞ 0
A[4][5] 60 A[4][2]+A[2][5]=∞+∞ ∞ 60

在原始邻接矩阵第五行中，挨个查找比较，计算与比较结果如下表所示：

第五行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[5][1] ∞ A[5][1]+A[1][1]=∞+∞ ∞ ∞
A[5][2] ∞ A[5][1]+A[1][2]=∞+0 ∞ ∞
A[5][3] ∞ A[5][1]+A[1][3]=∞+50 ∞ ∞
A[5][4] ∞ A[5][1]+A[1][4]=∞+∞ ∞ ∞
A[5][5] 0 A[5][1]+A[1][5]=0+∞ ∞ 0

整理每个表格中最后一列选择的实际路径，可以得到算法第二轮结果，即A^{2}

A2
0 10 60 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0

K=3

          k=3时，允许使用顶点3中转(在A^{2}的基础上)，那我们就需要在矩阵中遍历每一个值并按照下式比较大小，将二者中更小的那一个作为dist[i][j]当前路径的最小值。

#dist[i][3]+dist[3][j]就表示通过顶点3中转
dist[i][j]=min(dist[i][j],dist[i][3]+dist[3][j])
A^{2}（上一轮领接矩阵）
0 10 60 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0

在原始邻接矩阵第一行中,挨个查找比较，计算与比较结果若下表所示：

第一行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[1][1] 0 A[1][3]+A[3][1]=60+∞ ∞ 0
A[1][2] 10 A[1][3]+A[3][2]=60+∞ ∞ 10
A[1][3] 60 A[1][3]+A[3][3]=60+0 60 60
A[1][4] 30 A[1][3]+A[3][4]=60+∞ ∞ 30
A[1][5] 100 A[1][3]+A[3][5]=60+10 70 70

在原始邻接矩阵第二行中，挨个查找比较，计算与比较结果如下表所示：

第二行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[2][1] ∞ A[2][3]+A[3][1]=50+∞ ∞ ∞
A[2][2] 0 A[2[3]+A[3][2]=50+∞ ∞ 0
A[2][3] 50 A[2][3]+A[3][3]=50+0 ∞ 50
A[2][4] ∞ A[2][3]+A[3][4]=50+∞ ∞ ∞
A[2][5] ∞ A[2][3]+A[3][5]=50+10 60 60

在原始邻接矩阵第四行中，挨个查找比较，计算与比较结果如下表所示：

第四行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[4][1] ∞ A[4][3]+A[3][1]=20+∞ ∞ ∞
A[4][2] ∞ A[4][3]+A[3][2]=20+∞ ∞ ∞
A[4][3] 20 A[4][3]+A[3][3]=20+0 ∞ 20
A[4][4] 0 A[4][3]+A[3][4]=20+∞ ∞ 0
A[4][5] 60 A[4][3]+A[3][5]=20+10 30 30

在原始邻接矩阵第五行中，挨个查找比较，计算与比较结果如下表所示：

第五行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[5][1] ∞ A[5][3]+A[3][1]=∞+∞ ∞ ∞
A[5][2] ∞ A[5][3]+A[3][2]=∞+∞ ∞ ∞
A[5][3] ∞ A[5][3]+A[3][3]=∞+0 ∞ ∞
A[5][4] ∞ A[5][3]+A[3][4]=∞+∞ ∞ ∞
A[5][5] 0 A[5][3]+A[3][5]=0+10 ∞ 0

整理每个表格中最后一列选择的实际路径，可以得到算法第三轮结果，即A^{3}

A3
0 10 60 30 70
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0

 K=4

          k=4时，允许使用顶点4中转(在A^{3}的基础上)，那我们就需要在矩阵中遍历每一个值并按照下式比较大小，将二者中更小的那一个作为dist[i][j]当前路径的最小值。

#dist[i][4]+dist[4][j]就表示通过顶点4中转
dist[i][j]=min(dist[i][j],dist[i][4]+dist[4][j])
A^{3}（上一轮领接矩阵）
0 10 60 30 70
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0

在原始邻接矩阵第一行中,挨个查找比较，计算与比较结果若下表所示：

第一行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[1][1] 0 A[1][4]+A[4][1]=30+∞ ∞ 0
A[1][2] 10 A[1][4]+A[4][2]=30+∞ ∞ 10
A[1][3] 60 A[1][4]+A[4][3]=30+20 50 50
A[1][4] 30 A[1][4]+A[4[4]=30+0 30 30
A[1][5] 70 A[1][4]+A[4][5]=30+30 60 60

在原始邻接矩阵第二行中，挨个查找比较，计算与比较结果如下表所示：

第二行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[2][1] ∞ A[2][4]+A[4][1]=∞+∞ ∞ ∞
A[2][2] 0 A[2[4]+A[4][2]=∞+∞ 0 0
A[2][3] 50 A[2][4]+A[4][3]=∞+20 50 50
A[2][4] ∞ A[2][4]+A[4][4]=∞+0 ∞ ∞
A[2][5] 60 A[2][4]+A[4][5]=∞+30 60 60

在原始邻接矩阵第三行中，挨个查找比较，计算与比较结果如下表所示：

第三行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[3][1] ∞ A[3][4]+A[4][1]=∞+∞ ∞ ∞
A[3][2] ∞ A[3][4]+A[4][2]=∞+∞ ∞ ∞
A[3][3] 0 A[3][4]+A[4][3]=∞+20 0 0
A[3][4] ∞ A[3][4]+A[4][4]=∞+0 ∞ ∞
A[3][5] 10 A[3][4]+A[4][5]=∞+30 10 10

在原始邻接矩阵第五行中，挨个查找比较，计算与比较结果如下表所示：

第五行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[5][1] ∞ A[5][4]+A[4][1]=∞+∞ ∞ ∞
A[5][2] ∞ A[5][4]+A[4][2]=∞+∞ ∞ ∞
A[5][3] ∞ A[5][4]+A[4][3]=∞+20 ∞ ∞
A[5][4] ∞ A[5][4]+A[4][4]=∞+0 ∞ ∞
A[5][5] 0 A[5][4]+A[4][5]=∞+30 0 0

整理每个表格中最后一列选择的实际路径，可以得到算法第四轮结果，即A^{4}

A3
0 10 50 30 60
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0

  K=5

          k=4时，允许使用顶点4中转(在A^{3}的基础上)，那我们就需要在矩阵中遍历每一个值并按照下式比较大小，将二者中更小的那一个作为dist[i][j]当前路径的最小值。

#dist[i][5]+dist[5][j]就表示通过顶点5中转
dist[i][j]=min(dist[i][j],dist[i][5]+dist[5][j])
A^{4}（上一轮领接矩阵）
0 10 50 30 60
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0

在原始邻接矩阵第一行中,挨个查找比较，计算与比较结果若下表所示：

第一行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[1][1] 0 A[1][5]+A[5][1]=60+∞ ∞ 0
A[1][2] 10 A[1][5]+A[5][2]=60+∞ ∞ 10
A[1][3] 50 A[1][5]+A[5][3]=60+∞ ∞ 50
A[1][4] 30 A[1][5]+A[5][4]=60+∞ ∞ 30
A[1][5] 60 A[1][5]+A[5][5]=60+0 ∞ 60

在原始邻接矩阵第二行中，挨个查找比较，计算与比较结果如下表所示：

第二行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[2][1] ∞ A[2][5]+A[5][1]=60+∞ ∞ ∞
A[2][2] 0 A[2[5]+A[5][2]=60+∞ ∞ 0
A[2][3] 50 A[2][5]+A[5][3]=60+∞ ∞ 50
A[2][4] ∞ A[2][5]+A[5][4]=60+∞ ∞ ∞
A[2][5] 60 A[2][5]+A[5][5]=60+0 60 60

在原始邻接矩阵第三行中，挨个查找比较，计算与比较结果如下表所示：

第三行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[3][1] ∞ A[3][5]+A[5][1]=10+∞ ∞ ∞
A[3][2] ∞ A[3][5]+A[5][2]=10+∞ ∞ ∞
A[3][3] 0 A[3][5]+A[5][3]=10+∞ 0 0
A[3][4] ∞ A[3][5]+A[5][4]=10+∞ ∞ ∞
A[3][5] 10 A[3][5]+A[5][5]=10+0 10 10

在原始邻接矩阵第四行中，挨个查找比较，计算与比较结果如下表所示：

第五行更新情况
原始路径 路径长度 更新后的路径 更新后的路径长度 选择
A[4][1] ∞ A[4][5]+A[5][1]=30+∞ ∞ ∞
A[4][2] ∞ A[4][5]+A[5][2]=30+∞ ∞ ∞
A[4][3] 20 A[4][5]+A[5][3]=30+∞ ∞ ∞
A[4][4] 0 A[4][5]+A[5][4]=30+∞ ∞ ∞
A[4][5] 30 A[4][5]+A[5][5]=30+0 30 0

整理每个表格中最后一列选择的实际路径，可以得到算法第五轮结果，即A^{5}

A5
0 10 50 30 60
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0

        到这儿，Floyd算法结束，我们得到了最终的结果，每一轮算法迭代得到的结果如A^{1}，

A^{2}，A^{3}，A^{4}，A^{5}。大家在实际做题时建议按照这样的步骤来，不容易算错还比较方便。

总结

        以上便是Floyd算法的所有内容，如果对你有用，还请一键三连支持一下！

# 算法 # 数据结构
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

Dify Agent 智能体：让 AI 从“会聊天”升级为“能干活”

Dify Agent 是一种新型智能体应用，通过结合大语言模型与业务工具，将AI从被动应答升级为主动执行。它具备知识库查询、API调用、工作流编排等能力，可应用于企业客服、销售辅助、知识问答等场景。相比传统聊天机器人，Dify Agent能够理解任务目标、拆解执行步骤并调用实际业务系统完成操作，如同配备"工具箱"的数字员工。企业可通过配置Prompt、知识库、插件等组件，使AI助手具备业务流程处理

avatar DAMO开发者矩阵
cover

【案例分享】EVE-NG-v7园区-数据中心VXLAN多业务场景网络

avatar DAMO开发者矩阵
cover

多模态感知与环境理解技术向实时化与高精度演进

avatar DAMO开发者矩阵