Floyd算法：三行代码解决最短路径

        哈喽大家好！今天咱们来聊聊图论里超经典的 Floyd 算法 —— 这个能一次性算出所有节点之间最短路径的神奇算法。不管你是算法新手还是想复习的备考生，跟着我一步一步敲代码，保证你彻底搞懂它！

一、先搞懂：Floyd 算法到底能干啥？

        在开始写代码前，咱们得先明确问题：什么是多源最短路径？
简单说就是：给你一张带权图（可以有向也可以无向），要你求出任意两个节点之间的最短距离。

比如这样一张图:

我们需要知道 A 到 B、A 到 C、B 到 D… 所有成对节点的最短路径长度。

        Floyd 算法的优势就在于：用极其简洁的代码实现多源最短路径计算，核心逻辑甚至能浓缩成三重循环！（就是容易时间超限）

二、核心思想：动态规划的 "松弛" 魔法

        Floyd 算法的本质是动态规划，它的核心思路可以用一句话概括：
"从 i 到 j 的最短路径，要么直接走 i->j，要么经过某个中间点 k 走 i->k->j，取两者中更小的"用公式表示就是：

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

        这里的dist[i][j]表示从 i 到 j 的当前最短距离，我们通过不断尝试所有可能的中间点 k，来更新这个距离。

三、C++ 代码实现：从 0 到 1 写 Floyd

咱们用一个具体例子来实现：假设图有 4 个节点（0-3），邻接矩阵如下（INF 表示不可直达）：

步骤 1：初始化图（邻接矩阵）:

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9; // 用一个很大的数表示不可达

int main() {
// 节点数量
int n = 4;

// 初始化邻接矩阵
vector<vector<int>> dist(n, vector<int>(n, INF));

// 自身到自身的距离为0
for (int i = 0; i < n; i++) {
dist[i][i] = 0;
}

// 填充边的权重（根据上面的表格）
dist[0][1] = 5;
dist[0][3] = 10;
dist[1][2] = 3;
dist[2][3] = 1;

// 接下来就是Floyd的核心啦！
}

步骤 2：Floyd 核心三重循环:

// k是中间点
for (int k = 0; k < n; k++) {
// i是起点
for (int i = 0; i < n; i++) {
// j是终点
for (int j = 0; j < n; j++) {
// 松弛操作：如果i->k->j比i->j更短，就更新
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

划重点：外层循环必须是中间点 k！因为我们需要先确定中间点，再更新所有 i 到 j 的路径。

步骤 3：输出结果:

// 打印所有节点对的最短路径
cout << "各节点间的最短距离：" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == INF) {
cout << "INF ";
} else {
cout << dist[i][j] << " ";
}
}
cout << endl;
}

完整代码运行结果

各节点间的最短距离：
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0

来验证一下：比如 0 到 2 的最短路径，0->1->2（5+3=8），确实比直接走（INF）更短；0 到 3 的最短路径是 0->1->2->3（5+3+1=9），比直接走 0->3（10）更短，完美！

四、算法分析：时间与空间复杂度

• 时间复杂度：O (n³)，因为有三重嵌套循环，n 是节点数。所以 Floyd 算法适合节点数较少的场景（比如 n<1000）。
• 空间复杂度：O (n²)，主要用于存储邻接矩阵。

五、进阶思考：Floyd 的小细节

六、总结：什么时候用 Floyd？

当你需要：

• 计算所有节点对的最短路径
• 图中节点数量不多（n³ 能接受）
• 可能存在负权边（但无负权回路）

        Floyd 算法绝对是你的不二之选！它的代码简洁到让人惊叹，短短几行就能解决复杂的多源最短路径问题。

        好了，今天的 Floyd 算法就讲到这里～ 大家可以自己改改图的边权，试试不同的案例。如果有疑问，欢迎在评论区留言，咱们下期再见！记得点赞关注哦～