Floyd算法（知识点+模板）

Floyd算法知识点模板一、Floyd 和Dijkstra对比1. 两种最短路的核心区别Dijkstra单源最短路——一个起点跑向所有终点Floyd多源最短路——任意一点到任意一点的最短路径如果题目需要输出整张图的「点到点最短距离矩阵」唯一首选就是 Floyd。2. Floyd 独有优势Dijkstra 做不到支持负权边无负权环即可代码极简、无需建复杂邻接表天然维护全局最短路矩阵适合稠密图、小规模图算法类型负权复杂度适用场景Dijkstra单源不支持O((nm)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初始化距离矩阵自己到自己dist[i][i] 0有边相连赋值边权无边赋值无穷大INF步骤2三层循环顺序绝对不能乱外层k中转点DP阶段中层i起点内层j终点核心逻辑每次新增一个中转点全局更新所有点对最短路k 必须在最外层k 是 DP 的阶段动态规划枚举每一个中转点步骤3松弛更新先判断他们不是最大值如果i→k→j比直接i→j更短就更新五、题目练习【模板】B3647 【模板】Floyd - 洛谷#includebits/stdc.h using namespace std; const int N105; const int INF0x3f3f3f3f; // 无穷大数值很大相加不会int溢出 int dist[N][N]; // dist[i][j] 保存i到j的最短距离 int n,m; // n点数m边数 // Floyd‑Warshall算法求任意两点最短路 void floyd(){ // k是中转点必须放在最外层循环 for(int k1;kn;k){ for(int i1;in;i){ // i起点 for(int j1;jn;j){ // j终点 // 只有i→k 和 k→j 都可达才可以更新i→j if(dist[i][k]!INFdist[k][j]!INF){ dist[i][j]min(dist[i][j],dist[i][k]dist[k][j]); } } } } } int main(){ cinnm; // 初始化距离矩阵 for(int i1;in;i){ for(int j1;jn;j){ if(ij){ // 自己到自己距离为0 dist[i][j]0; } else{ // 初始其它点之间不可达赋值无穷大 dist[i][j]INF; } } } // 读入m条无向边 for(int i1;im;i){ int u,v,w; cinuvw; // min处理重边保留两点之间权值最小的边 dist[u][v]min(dist[u][v],w); dist[v][u]min(dist[v][u],w); } floyd(); // 执行Floyd求全源最短路 // 输出距离矩阵 for(int i1;in;i){ for(int j1;jn;j){ if(dist[i][j]INF) // 两点不可达输出0 cout0 ; else coutdist[i][j] ; } coutendl; } return 0; }Floyd能处理负权不能处理负权环存在负权环时路径可以无限变短最短路不存在。判定负权环跑完后dist[i][i] 0即为存在负环。