想象你是个快递员，手里有N个城市的地图，每个城市之间可能有直达航班（正权边）或劫匪出没的路线（负权边）。现在老板突然问：“从任意A城到任意B城的最低成本是多少？” 暴力枚举所有起点？O(N²)的复杂度瞬间让你怀疑人生——这时候Floyd-Warshall算法就像你的外挂，能一次性计算出所有点对间的最短路径！
核心概念讲解
这个算法的核心思想是动态规划。我们定义一个三维状态矩阵dist[i][j][k]表示"经过前k个中间节点时，i到j的最短距离"，但实际实现时会压缩成二维数组：
$$
\text{dist}[i][j] = \begin{cases}
w_{ij} & (i=j) \
\infty & (\text{无边}) \
\min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j]) & \text{其他}
\end{cases}
$$
关键点：
松弛操作：每次用中间节点k来更新i→j的路径
三重循环：外层遍历中间节点k，内层遍历所有i,j对
负权环检测：若最终
dist[i][i]<0说明存在负权环（比如某些城市物价暴跌到亏钱！）
图示：
初始图： A --5-- B --3-- C
\ / /
\ / /
X --2---Y
Floyd过程：
先用X更新A→C: min(∞, A→X→Y→C=5+2+3=10) → 实际会先发现更优路径
C++代码示例
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f; // 大数替代无穷大
void floyd(int n, vector<vector<int>>& graph) {
vector<vector<int>> dist(n, vector<int>(n));
// 初始化：直接赋值graph，对角线为0，无边为INF
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
dist[i][j] = graph[i][j];
// 三重循环：k是中间节点，i,j是起点终点
for(int k = 0; k < n; ++k) { // 外层：尝试所有中转站
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(dist[i][k] != INF && dist[k][j] != INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main() {
// 输入格式：第一行n，接下来n×n矩阵（-1表示无边）
int n;
cin >> n;
vector<vector<int>> graph(n, vector<int>(n));
for(auto &row : graph)
for(auto &x : row)
x = cin() == -1 ? INF : x;
floyd(n, graph);
// 输出结果
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(dist[i][j] == INF) cout << "∞ ";
else cout << dist[i][j] << ' ';
}
cout << endl;
}
return 0;
}
算法分析
时间复杂度：O(N³)，适合N≤400的稠密图（竞赛中常见上限）
空间复杂度：O(N²)，需要保存N×N的距离矩阵
特点：
✅ 一次计算所有点对最短路，适合多查询场景
❌ 不擅长稀疏图（此时Dijkstra+堆优化更优）
❌ 负权边可用，但若存在负权环则结果无效（需额外判断）
经典例题
题意：带负权边的最短路，要求判断是否存在负权环
解法：Floyd最后检查对角线，若dist[i][i]<0即存在
- 虽然树结构看似简单，但题目要求处理负边和环，Floyd是稳妥选择
推荐练习
[入门] 洛谷 P1118 关路灯（多源最短路基础应用）
[进阶] 洛谷 P2946 旅行商问题（TSP预处理阶段常用来求所有点对距离）
[拔高] AtCoder D1T3 - Negative Cycle（负权环检测实战）
小结
一句话记住：Floyd-Warshall是"懒人算法"，用空间换时间，适合需要频繁查询任意两点距离的场景。下篇文章将教你如何用Johnson算法在稀疏图中结合Dijkstra和Bellman-Ford，让负权边也能跑出最快的最短路！
**
🌐 友情链接： 欢迎访问我们的国际版站点 noiquest.com - 全球算法竞赛资源分享平台
💬 互动时间：你在学习过程中有什么疑问？在评论区告诉我，我会选择有代表性的问题详细解答！
📚 相关推荐：