企业官网建设流程全解析

Floyd算法（知识点+模板）

一、Floyd 和Dijkstra对比

1. 两种最短路的核心区别

• Dijkstra：单源最短路——一个起点，跑向所有终点
• Floyd：多源最短路——任意一点到任意一点的最短路径

如果题目需要输出整张图的「点到点最短距离矩阵」，唯一首选就是 Floyd。

2. Floyd 独有优势（Dijkstra 做不到）

• 支持负权边（无负权环即可）
• 代码极简、无需建复杂邻接表
• 天然维护全局最短路矩阵，适合稠密图、小规模图

二、 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：初始化距离矩阵

1. 自己到自己：dist[i][i] = 0
2. 有边相连：赋值边权
3. 无边：赋值无穷大INF

步骤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即为存在负环。