Floyd算法（知识点+模板）
一、Floyd 和Dijkstra对比
1. 两种最短路的核心区别
- Dijkstra：单源最短路——一个起点，跑向所有终点
- Floyd：多源最短路——任意一点到任意一点的最短路径
如果题目需要输出整张图的「点到点最短距离矩阵」，唯一首选就是 Floyd。
2. Floyd 独有优势（Dijkstra 做不到）
- 支持负权边（无负权环即可）
- 代码极简、无需建复杂邻接表
- 天然维护全局最短路矩阵，适合稠密图、小规模图
| Dijkstra | 单源 | 不支持 | O((n+m)logn) | 大图、稀疏图、多次单查 |
| Floyd | 多源 | 支持 | O(n³) | 小图、稠密图、全局矩阵 |
二、 Floyd 核心思想
Floyd 的本质：枚举每一个点作为「中转点」，不断松弛更新全局最短路。
假设你在城市里走路，想找 A → B 的最短路径。
最朴素想法：直接走 A→B。
但 Floyd 的思考是：
我能不能先绕一下别的中转站，让路程更短？
比如：
A → C → B 会不会比 A→B 更近？
A → D → B 会不会更短？
A → C → D → B 会不会更短？
所有最短路，一定是「经过若干中转点」的最优结果。
三、Floyd 是动态规划？！
Floyd 不是暴力，是二维 DP 滚动优化！
1. 原始 DP 状态
定义：dp[k][i][j]
含义：只允许经过前 k 个点作为中转时，i 到 j 的最短距离
2. DP 转移方程
d
p
[
k
]
[
i
]
[
j
]
=
min
(
d
p
[
k
−
1
]
[
i
]
[
j
]
,
d
p
[
k
−
1
]
[
i
]
[
k
]
+
d
p
[
k
−
1
]
[
k
]
[
j
]
)
dp[k][i][j] = \\min(dp[k-1][i][j],\\ dp[k-1][i][k] + dp[k-1][k][j])
dp[k][i][j]=min(dp[k−1][i][j], dp[k−1][i][k]+dp[k−1][k][j])
- 方案1：不经过 k 点，沿用旧最短路 dp[k-1][i][j]，从i 到 j。
- 方案2：经过 k 点中转，i→k→j，从i到k 再到 j。
- 两者取最小值，就是当前最优解
3. 空间优化（最终版 Floyd）
观察发现：第 k 层只依赖 k-1 层，可以压掉一维
二维滚动数组：dist[i][j]
最终公式：
d
i
s
t
[
i
]
[
j
]
=
min
(
d
i
s
t
[
i
]
[
j
]
,
d
i
s
t
[
i
]
[
k
]
+
d
i
s
t
[
k
]
[
j
]
)
dist[i][j] = \\min(dist[i][j],\\ dist[i][k] + dist[k][j])
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
Floyd 只有三重循环：外层 k 是 DP 阶段，内层 i、j 是状态遍历。
四、算法完整流程
步骤1：初始化距离矩阵
步骤2：三层循环（顺序绝对不能乱）
外层 k：中转点（DP阶段）
中层 i：起点
内层 j：终点
核心逻辑：每次新增一个中转点，全局更新所有点对最短路
k 必须在最外层！k 是 DP 的阶段，动态规划，枚举每一个中转点
步骤3：松弛更新
先判断他们不是最大值，如果 i→k→j 比直接 i→j 更短，就更新
五、题目练习【模板】
B3647 【模板】Floyd – 洛谷
#include<bits/stdc++.h>
using namespace std;
const int N=105;
const int INF=0x3f3f3f3f; // 无穷大，数值很大，相加不会int溢出
int dist[N][N]; // dist[i][j] 保存i到j的最短距离
int n,m; // n点数，m边数
// Floyd‑Warshall算法：求任意两点最短路
void floyd(){
// k是中转点，必须放在最外层循环！
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){ // i起点
for(int j=1;j<=n;j++){ // j终点
// 只有i→k 和 k→j 都可达，才可以更新i→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;
// 初始化距离矩阵
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
// 自己到自己距离为0
dist[i][j]=0;
}
else{
// 初始其它点之间不可达，赋值无穷大
dist[i][j]=INF;
}
}
}
// 读入m条无向边
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
// min处理重边：保留两点之间权值最小的边
dist[u][v]=min(dist[u][v],w);
dist[v][u]=min(dist[v][u],w);
}
floyd(); // 执行Floyd求全源最短路
// 输出距离矩阵
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i][j]==INF)
// 两点不可达，输出0
cout<<"0"<<" ";
else
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
Floyd能处理负权，不能处理负权环
存在负权环时，路径可以无限变短，最短路不存在。
判定负权环：跑完后 dist[i][i] < 0 即为存在负环。
