当前位置：首页 > news >正文

Floyd算法：3行代码搞定全源最短路

news 2026/6/1 8:25:19

一、上期回顾

掌握SPFA 算法，解决带负权边的最短路问题，并且可以判断负环。今天学习图论最短路最后一个核心算法：Floyd 算法，专门求所有点到所有点的最短路径。

二、Floyd 核心概念

1. 解决什么问题

给定一个图（有向 / 无向、可带负权），求出任意两点 i 到 j的最短路径。

多源最短路：起点和终点都是任意的
优点：代码极简，3 层循环搞定，不用队列、不用堆
缺点：复杂度较高 \(O(n^3)\)，只适合小规模图（n ≤ 500）

2. 核心思想（动态规划 DP）

中转站思想：对于任意两点i → j，判断是否经过中间点 k能更近：

i → j 直接走 i → k → j 绕一下

取距离最小的那个。

三、数据结构

Floyd 必须用邻接矩阵存图：

const int N = 505; const int INF = 0x3f3f3f3f; // 用这个无穷大，相加不溢出 int dist[N][N]; // dist[i][j] 表示 i 到 j 的最短距离

四、Floyd 万能模板（必背，3 行核心）

#include <iostream> #include <cstring> using namespace std; const int N = 505; const int INF = 0x3f3f3f3f; int dist[N][N]; int n, m; // n 个点，m 条边 void init() { // 1. 初始化：自己到自己距离 0，其余无穷大 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dist[i][j] = (i == j) ? 0 : INF; } void floyd() { // 核心 3 层循环！！！顺序不能变：k -> i -> j for (int k = 1; k <= n; k++) // 中转点 for (int i = 1; i <= n; i++) // 起点 for (int j = 1; j <= n; j++)// 终点 // 松弛操作：i->k->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() { cin >> n >> m; init(); // 建图 for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; dist[u][v] = min(dist[u][v], w); // 重边取最小 // 无向图：dist[v][u] = min(dist[v][u], w); } floyd(); // 输出任意两点距离 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist[i][j] == INF) cout << "-1 "; else cout << dist[i][j] << " "; } cout << endl; } return 0; }

五、关键要点（死记硬背）

循环顺序绝对不能错
- 最外层：中转点 k
- 中间：起点 i
- 最内层：终点 j
无穷大推荐用0x3f3f3f3f
- 比INT_MAX安全，两个相加不会溢出
判不可达
```
if (dist[i][j] == INF) 不可达
```

六、三大最短路算法终极对比

表格

算法	类型	数据结构	复杂度	适用场景
Dijkstra	单源	堆	\(O(E \log V)\)	无负权，大数据图
SPFA	单源	队列	不稳定	有负权，判负环
Floyd	多源	矩阵	\(O(n^3)\)	任意两点，小数据