【狂热算法篇】探秘图论之 Floyd 算法：解锁最短路径的神秘密码(通俗易懂版)

                   ： 羑悻的小杀马特.-CSDN博客羑悻的小杀马特.擅长C/C++题海汇总,AI学习,c++的不归之路,等方面的知识,羑悻的小杀马特.关注算法,c++,c语言,青少年编程领域.https://blog.csdn.net/2401_82648291?spm=1010.2135.3001.5343  

在本篇文章中，博主将带大家去学习所谓的Floyd算法；从基本理解，画图分析展示，再到最后的代码实现，以及为何要这样实现代码，等一些细节问题做解释，相关题型应用，非常值得哟，尤其是刚入门的小白学习；干货满满，通俗易懂；欢迎大家点赞收藏阅读呀！！！ 

 欢迎拜访：羑悻的小杀马特.-CSDN博客

本篇主题：秒懂百科之Floyd算法的深度剖析

制作日期：2025.01.17

隶属专栏：美妙的算法世界

 下面一起开始这场旅行吧：

目录

一·Floyd 算法介绍：

1.1算法背景与定义：

1.2 实例分析：

 1.3算法原理：

1.3.1初始化操作：

1.3.2动态规划递推过程：

1.3.3算法结束后的结果：

1.4算法复杂度：

1.4.1时间复杂度：

1.4.2空间复杂度：

二·Floyd算法代码实现及剖析：

填表时为何i到j会出现多个中间点：

滚动数组优化： 

k循环为什么套在最外层：

三·Floyd算法例题应用：

四·Floyd算法适用的算法题类型： 

4.1最短路径问题（所有顶点对）：

4.2传递闭包问题（在有向图中）：

4.3图的连通性判断（在有权图中）：

4.4动态更新最短路径的问题：

五·Floyd算法实际应用场景：

5.1交通网络规划：

5.2计算机网络路由：

5.3游戏地图导航：

六·本篇小结：

一·Floyd 算法介绍：

下面我们不会直接把版子搬上来，这样大家可能会不太明白，而是通过形象的例子去模拟推导它的思路然后再把它转化成代码。

1.1算法背景与定义：

Floyd 算法（弗洛伊德算法）是一种用于解决图中多源最短路径问题的经典动态规划算法。它能够求出图中任意两个顶点之间的最短路径长度。这个图可以是有向图，也可以是无向图。例如，在一个交通网络中（以城市为顶点，道路为边），Floyd 算法可以帮助我们找到任意两个城市之间的最短行车距离。

1.2 实例分析：

这里上面说了无向图和有向图都适合，但是我们这里就里特别的有向图进行演示一遍是如何操作的（当然后面如果去实现代码的话只需要填给定权值的时候始终点在交换填充一次就OK了）

我们以下面的有向图为例子：

我们应用Floyd算法的思路：首先就是先搞一个邻接矩阵（b）和一个记录终节点的前驱一个节点的矩阵（h）（也就是这两个矩阵）；接下来我们先把这两个矩阵初始化。

根据上图完成刚开始的初始化工作：

先解释下：行代表起始点的编号；而列代表的是终止点的标号。

对于b矩阵：对应的值是从起始点到终止点最小距离；-->为了找到给定节点最短路径长度

对于h矩阵： 对应的值表示的是从起始点到终止点的路径中；终止点前一个节点的标号。-->为了推导出最小路径长度所选择的路径所经节点有哪些。

b和h表的约定： 

然后我们可以知道b表：自己到自己是不需要距离的故初始化为0；而如果两点之间无路径就初始化为无穷即可（当然了这样定义起来也是比较舒服的）； 对h表如果无法到达前驱就是-1。

然后我们要知道如果存在最小路径：它可能是直接到达终止点；还可能是一路上通过了一些中间点到达的。因此我们就需要一个个的遍历；也就是让这些点依次作为中间点去选择最小的路径，然后依次更新表：

下面，我们就以上面画的图为例；依次从0,1,2分别依次作为中间点去填表；那么我们最后把所有的点的情况都作为中间点考虑后，最后一次填完表 ；表中就出现的都是最小路径（这里其实，每次填表其实相当于对原表进行选择性覆盖）。

分析0作为中间节点：完成填表：

b表：我们需要由i到0然后再由0到j总的路径和如果和之前的路径比较，如果变小了说明需要更新否则照抄即可（也就是说明我们拿0作为中间点，相当于不合适，保持之前的路径） 

h表：这里我们要存放的是终止点的前一个即可：可以这么填：（如果b表对于位置的值不是照抄，那么就换成当前遍历到的待定中间点即可，否则就不变）

 因此按照我们上文划线的规定填表规则依次向后填充即可；下面就是1,2了：

以1作为中间节点：

以2作为中间节点（也就是存放最后最短路径的表了） ：

最后我们可以根据路线图选择最短路径来验证一下它的正确性；为了好理解，我们举的是3个结点的例子，更多结点也是一样做法（可能会问这样每次都填一次表是不是麻烦；要记住我们依靠的是计算机来实现只需要后面利用动归即可）。 

小总结：我们之所以来这样举例模拟，就是为了后面为我们理解Floyd算法是那样设计的整个小铺垫，相信我们弄懂了上面这些操作是和进行的，那么后面算法实现就会有种恍然大悟的感觉啦。 

 1.3算法原理：

假设我们有一个包含 n 个顶点的图G=(V,E) ，其中  V是顶点集合，E 是边集合。我们使用一个二维数组d[i][j]  来表示顶点 i 到顶点 j 的最短路径长度估计。

1.3.1初始化操作：

当没有引入任何中间顶点时， d[i][j]的初始值为边 (i,j)的权值。如果 i=j，则 d[i][j]=0，因为一个顶点到自身的距离为 0；如果顶点  i和 j 之间没有直接边相连，那么d[i][j] 初始化为一个足够大的值（比如在编程中可以用一个很大的常量0x3f3f3f3f(int)(保证相加不越界，后面会说)来表示无穷大）。

1.3.2动态规划递推过程：

对于每一个中间顶点 k（从 1 到 n），我们检查是否可以通过这个中间顶点来缩短从顶点i  到顶点 j 的路径。更新公式为：

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

这个公式的含义是，比较原来从 i 到 j 的最短路径估计值和经过中间顶点  k的路径长度（即从 i 到k的距离加上从  k到j 的距离），如果经过k的路径更短，就更新d[i][j] 的值。

1.3.3算法结束后的结果：

当所有的中间顶点都被考虑过后， d[i][j]中存储的就是顶点i到顶点j的最短路径长度。

1.4算法复杂度：

1.4.1时间复杂度：

Floyd 算法的时间复杂度是 O(N^3)。这是因为算法中有三层嵌套的循环，每层循环最多执行 n 次，所以总的时间复杂度是 N*N*N=N^3。

1.4.2空间复杂度：

算法需要一个二维数组来存储最短路径长度，所以空间复杂度是O(N^2) 。

二·Floyd算法代码实现及剖析：

 下面我们先把版子放在这，大家如果可以根据上面模拟的例子看懂就更好了，不懂的话，我们后面会一一剖析的（以有向图为例）这里对于节点的编号我们和上面例子变一下，从1开始。（一般输入都是结点编号都是默认从1开始）。

floyd模版： 

void floyd(vector<vector<ll>>&dp) {
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);


}

或许大家刚开始确实看不懂，因为上面的模版是我们从三维表示利用滚动数组优化降维后的表示（使得每次填表都会进行重新覆盖操作）；那么下面我们就一步步分析代码是如何实现的吧：

上面我们不是根据依次遍历编号节点去填表嘛（这里我们就不考虑上面的h表的实现，只考虑b表的实现） ：

首先我们先明确状态方程的定义：

先定义三维即dp[k][i][j]：表示当选择起始点为i，终止点为j的时候从i到j在中间经过的中间点不超过k个的时候最短路径。（这里先写三维状态方便我们理解，之后改写代码在做降维处理及解释）

 是不是还会有点迷糊对这个定义；下面我们再细说一下：

迷惑的应该是这个k是怎么规定的：

所谓的不超过k：

填表时为何i到j会出现多个中间点：

我们上面不是模拟了一下根据节点的个数去依次作为中间点去填表嘛（其实这里就是把这个过程转化成了代码）：也就是我们每次会选择一个节点作为中间点；这就可能会得到它符合要求（以它作为中间点的话，我们可以比之前更短路径，因此就更新了b表）；此后我们又遍历到令一个节点分析它作为中间点，又用到了上次被替换的i与j；分析后第二个中间点也成立；因此我们当前的i就会经历多个中间点然后到j。

下面我们画图形象展示一下：

这里我们首先以3作为1到4的中间点（注：在这之前值存的是1-2-4为13）（此前我们已经获得了3到4的最短路径也就是3-2-4，然后更新了对应b表值），然后再取min发现13就大于5+3了，即更新此刻就是1-3-2-4了；那么我们就会发现我们在每次填充b表值的时候每个最小路径值可以代表含有多个中间节点；那么k就是对它的约束。

 因此这里我们就明白为了要不超过k了；这里我们给节点按照升序排列；遍历到当前的k；那么它由i到j中间通过的节点数一定是小于等于k的。

①下面分析下状态转移方程吧：

首先我们在上面理解了这个k的相关含义，因此当我们遍历到第k个时候，dp里面存的最小路径长度里面所包含的中间节点个数肯定就是小于k咯（因为此刻到k还没开始更新）：

因此我们可以不选k号，也可以选（当然根据长度变化最后更新（min））:不选的话就是，由i到j就是不超过k-1，选的话就是借助k这个点，先从i到k再从k到j。  哈哈，下面得出状态转移方程：

滚动数组优化： 

这里是三维的是不是看上去有点复杂；因为它每次我们可以看到用到的都是上一次的值，也就是刚刚填完的k-1的值，此时可以考虑滚动数组优化 ；直接把下一次的覆盖过去；降成二维即可。

这里倒序到是不用，直接把与k关的下标干掉（注意k这层循环不能去掉）即可：

k循环为什么套在最外层：

这里我们肯定是可以根据上面我们模拟的例子来写代码了，但是可能会有个疑问，为什么k要在最外层而不是最内层，①因为这里我们是把当前k固定看做中间点了；②或者还可以这么理解：上面我们画图分析每次如何填写b表；是先固定完这个k然后填完一次表再接着固定再来；因此这就是为什么k要在最外层的原因了。

②这里我们考虑的是先初始化好我们的b表：

这里我们得根据题意分析如何进行初始化（也就是在没有填充有向变的权的时候）：

这里由于我们要的是最小值因此数组先全都搞成最大值；难道这里还是要搞INT_MAX这样的嘛？这就错了，我们之后可能会对这个表里的值先相加判断是不是最小路径（后面会说到）；那么此时就越界了，因此选用的是0x3f3f3f3f（整型）；至于为什么？请观看博主的另一篇博客有讲解：  【动态规划篇】步步带你深入解答成功AC最优包含问题（通俗易懂版）-CSDN博客

    如果让你恍然大悟，新知识涌入大脑，可以给博主的文章点个赞嘛！！！

其次呢就是右斜对角线：即行=列：一个点到一个点它自己的距离最短肯定就是0了；因此初始化，只要记住这两个细节就ok啦。

 vector<vector<ll>>dp(N + 1, vector<ll>(N + 1, 0x3f3f3f3f3f3f3f3f));
for (int i = 1; i < N + 1; i++) for (int j = 1; j < N + 1; j++)dp[i][j] = i == j ? 0 ：dp[i][j];//这里以long long为例；int类似

③ 下面就是填充边的权值：

这里，根据我们题意所给的权值分两种情况：有向图和无向图填权值会有所不同，最终的求法也会不同：

有向图：

我们就直接填写就好：但是并不是真正的直接填入dp表；比如我们对有的边有多条边的权值被给出；那么就不能直接填了（因为我们要求填完第一次权值dp表内是已给出的最小路径长度，因此我们填写的时候对原先值取min即可）。

如果我们没有给权值就以为这无通路；自然举例就是我们的无穷（之前默认初始化的）。

 dp[i][j] = min(v, dp[i][j]);//保证加完权值dp值一定是所输入时候最小的

 无向图：

这里其实就是给了我们的两点和val只不过起始点和终止点是可以互换的（也就是有向图只能从起始点到终止点，而无向图还可以从终止点回到起始点。）故只需要i，j互换一下再填写即可。

 dp[i][j] = min(v, dp[i][j]);//保证加完权值dp值一定是所输入时候最小的
 dp[j][i] = min(v, dp[j][i]);//保证加完权值dp值一定是所输入时候最小的

 下面我们就直接调用Floyd函数完成填表即可；那么最后dp表里的值就是我们对应的i到j的最短路径长度了。

再下面就是询问了：

我们要明白分两种情况：

1.边权有负数的情况（负数路径是不算的）：这时候当我们取相加取min就会发现变小；因此最后我们要根据题目权所给的范围来判断什么时候是无路径的。

2.都是正数：那么每次都是取min也就是原表还是0x3f3f3f3f的地方就是无路径的。

那么我们就完成啦对Floyd算法相关剖析了，

相信大家肯定有不同看法，学习到了吧！ 

三·Floyd算法例题应用：

 下面我们就以一道无向图为例（无负数权值）：

测试用例：

输入：

3 3 3

1 2 1

1 3 5

2 3 2

1 2

1 3

2 3 

 输出:

1

3

2 

原题链接：  蓝桥账户中心

下面就直接按照我们上述讲的搬过去即可（不过这里注意一下数据相加过大用long long）：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;//这里floyd求最短路径的时候会出现dp之和；假设存在的w都是10^9那么相加就会出现越界；
ll N, M, Q;
void floyd(vector<vector<ll>>&dp) {
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);


}

int main()
{
    cin >> N >> M >> Q;
    vector<vector<ll>>dp(N + 1, vector<ll>(N + 1, 0x3f3f3f3f3f3f3f3f));
    //dp表初始化：
    for (int i = 1; i < N + 1; i++) for (int j = 1; j < N + 1; j++)dp[i][j] = i == j ? 0 : dp[i][j];
    //填充给出的权值：
    while (M--) {
         int i, j;ll v;
        cin >> i >> j >> v;
        //边是双向的：
        dp[i][j] = min(v, dp[i][j]);//保证加完权值dp值一定是所输入时候最小的
        dp[j][i] = min(v, dp[j][i]);//保证加完权值dp值一定是所输入时候最小的
    }
    floyd(dp);
    //询问去访问对应dp值：
    while (Q--) {
         int i, j;
        cin >> i >> j;
        //if(dp[i][j]>=0x3f3f3f3f/2) cout<<"-1"<<endl;负数权值情况
        if (dp[i][j] == 0x3f3f3f3f3f3f3f3f) cout << -1 << endl;
        else cout << dp[i][j] << endl;
    }

    return 0;
}

其他相关的题也不过是版子做一下修改即可。    

四·Floyd算法适用的算法题类型： 

4.1最短路径问题（所有顶点对）：

例如：

给定一个城市交通网络，其中城市是顶点，道路是边，边的权值表示道路的长度。求任意两个城市之间的最短距离。这种情况下，Floyd 算法可以直接应用，通过构建城市交通网络的邻接矩阵，运行 Floyd 算法后，就可以得到所有城市对之间的最短距离。

4.2传递闭包问题（在有向图中）：

传递闭包定义：在一个有向图  G=(V,E)中，对于顶点 u,v属于V，如果从u到v存在一条有向路径（路径长度可以是任意正整数），那么在传递闭包图中就有一条从u到v的边。

例如：

有一个社交网络关系图，其中顶点是人，边表示关注关系（有向边）。判断任意两个人之间是否存在关注路径（间接关注也算）。可以将 Floyd 算法用于解决这个问题，把图的邻接矩阵中的边权值设置为 1（表示存在关系）或者 0（表示不存在关系），运行 Floyd 算法后，如果 d[i][j] 不为 0，则表示从 i到 j存在关注路径。 

4.3图的连通性判断（在有权图中）：

例如：

在一个通信网络中，每个节点代表一个通信基站，边代表基站之间的通信链路，边的权值表示链路质量。判断任意两个基站之间是否能够通信（可能通过其他基站中转）。通过 Floyd 算法计算最短路径，如果 d[i][j] 不是无穷大，则表示基站 i和j之间可以通信。

4.4动态更新最短路径的问题：

例如：

在一个物流配送网络中，边的权值可能会因为交通状况等因素动态变化。最初可以使用 Floyd 算法计算出所有仓库之间的最短路径。当某条边的权值改变后，可以再次运行 Floyd 算法（或者根据 Floyd 算法的原理部分更新受影响的路径）来重新计算最短路径，以适应网络的变化。

五·Floyd算法实际应用场景：

5.1交通网络规划：

在城市交通网络中，交通部门可以利用 Floyd 算法计算各个城市之间的最短路径，以便规划最优的公交线路、高速公路路线等。

例如，在一个区域内有多个城市，城市之间有不同长度的道路连接，通过 Floyd 算法可以找到任意两个城市之间的最短行车路线，帮助交通部门合理布局交通资源，提高交通效率。

5.2计算机网络路由：

在计算机网络中，网络管理员可以使用 Floyd 算法来确定数据包在不同节点之间传输的最短路径。这对于优化网络拓扑结构、提高网络性能和减少传输延迟非常重要。

例如，在一个企业内部网络或者互联网服务提供商的网络中，通过 Floyd 算法找到数据中心和用户终端之间的最优传输路径，确保数据能够快速、高效地传输。

5.3游戏地图导航：

在游戏开发中，特别是一些角色扮演游戏或者策略游戏，游戏地图往往是一个复杂的图结构。Floyd 算法可以用于实现游戏中的地图导航功能，帮助玩家找到从一个地点到另一个地点的最短路径。

比如在一个大型多人在线角色扮演游戏（MMORPG）中，玩家在一个庞大的游戏世界中需要从一个城镇前往另一个城镇，游戏系统可以利用 Floyd 算法为玩家提供最短的行走路线，增强游戏体验。

六·本篇小结：

Floyd算法和Dijkstra算法对比（文末）传送门：   

 通过本篇对Floyd算法介绍，我们会对它有一个全新的认识；那么下面我们就总结一下：

首先就是版子，大家最好理解，或者也可以直接背；其次就是操作的流程：根据题意先初始化化表-->根据给定的边权完成加边权操作（注意有向图还是无向图）--->调用Floyd函数-->进行询问（注意边权正负数情况）。

最后感谢大家阅读呀！！！！