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}(原始邻接矩阵)
010∞30100
∞050∞∞
∞∞0∞10
∞∞20060
∞∞∞∞0

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

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

第二行更新情况
原始路径路径长度更新后的路径更新后的路径长度选择
A[2][1]∞A[2][1]+A[1][1]=∞+0∞∞
A[2][2]0A[2][1]+A[1][2]=∞+10∞0
A[2][3]50A[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]0A[3][1]+A[1][3]=∞+∞∞0
A[3][4]∞A[3][1]+A[1][4]=∞+30∞∞
A[3][5]10A[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]20A[4][1]+A[1][3]=∞+∞∞20
A[4][4]0A[4][1]+A[1][4]=∞+30∞0
A[4][5]60A[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]0A[5][1]+A[1][5]=∞+100∞0

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

A1
010∞30100
∞050∞∞
∞∞0∞10
∞∞20060
∞∞∞∞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}(上一轮邻接矩阵)
010∞30100
∞050∞∞
∞∞0∞10
∞∞20060
∞∞∞∞0

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

第一行更新情况
原始路径路径长度更新后的路径更新后的路径长度选择
A[1][1]0A[1][2]+A[2][1]=10+∞∞0
A[1][2]10A[1][2]+A[2][2]=10+01010
A[1][3]∞A[1][2]+A[2][3]=10+506060
A[1][4]30A[1][2]+A[2][4]=10+∞∞30
A[1][5]100A[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]0A[3][2]+A[2][3]=∞+50∞0
A[3][4]∞A[3][2]+A[2][4]=∞+∞∞∞
A[3][5]10A[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]20A[4][2]+A[2][3]=∞+50∞20
A[4][4]0A[4][2]+A[2][4]=∞+∞∞0
A[4][5]60A[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]0A[5][1]+A[1][5]=0+∞∞0

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

A2
0106030100
∞050∞∞
∞∞0∞10
∞∞20060
∞∞∞∞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}（上一轮领接矩阵）
0106030100
∞050∞∞
∞∞0∞10
∞∞20060
∞∞∞∞0

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

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

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

第二行更新情况
原始路径路径长度更新后的路径更新后的路径长度选择
A[2][1]∞A[2][3]+A[3][1]=50+∞∞∞
A[2][2]0A[2[3]+A[3][2]=50+∞∞0
A[2][3]50A[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+106060

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

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

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

第五行更新情况
原始路径路径长度更新后的路径更新后的路径长度选择
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]0A[5][3]+A[3][5]=0+10∞0

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

A3
010603070
∞050∞60
∞∞0∞10
∞∞20030
∞∞∞∞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}（上一轮领接矩阵）
010603070
∞050∞60
∞∞0∞10
∞∞20030
∞∞∞∞0

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

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

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

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

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

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

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

第五行更新情况
原始路径路径长度更新后的路径更新后的路径长度选择
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]0A[5][4]+A[4][5]=∞+3000

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

A3
010503060
∞050∞60
∞∞0∞10
∞∞20030
∞∞∞∞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}（上一轮领接矩阵）
010503060
∞050∞60
∞∞0∞10
∞∞20030
∞∞∞∞0

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

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

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

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

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

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

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

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

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

A5
010503060
∞050∞60
∞∞0∞10
∞∞20030
∞∞∞∞0

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

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

总结

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

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

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

更多推荐

智能语音机器人选型技术指南：意图识别率、方言覆盖与情绪感知的评估方法

本文解析智能语音机器人选型的三个硬指标：意图识别率、方言覆盖与情绪感知，给出各指标的评估方法、测试要点与选型建议，帮助企业避开只看单一数字的选型误区。

avatar DAMO开发者矩阵

端到端深度学习 vs 传统三段式架构：智能语音机器人的技术分水岭

本文对比端到端深度学习与传统三段式架构在智能语音机器人中的差异，分析端到端在低延迟、情感感知上的优势及数据稀缺、可解释性差的挑战，并介绍一体化原生架构作为务实落地路径。

avatar DAMO开发者矩阵
cover

机器人在家里怎么认路、怎么认出你？一文看懂“感知“到底在干什么

avatar DAMO开发者矩阵