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

一、上期回顾掌握SPFA 算法解决带负权边的最短路问题并且可以判断负环。 今天学习图论最短路最后一个核心算法Floyd 算法专门求所有点到所有点的最短路径。二、Floyd 核心概念1. 解决什么问题给定一个图有向 / 无向、可带负权求出任意两点 i 到 j的最短路径。多源最短路起点和终点都是任意的优点代码极简3 层循环搞定不用队列、不用堆缺点复杂度较高 \(O(n^3)\)只适合小规模图n ≤ 5002. 核心思想动态规划 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)\)任意两点小数据七、今日核心总结Floyd 是多源最短路求任意 i 到 j 的距离核心代码3 层循环顺序k → i → j基于 DP 思想用中转站松弛更新距离代码极简适合笔试快速默写数据量大绝对不能用会超时八、课后练习手写 Floyd 模板建一个 4 个点的图输出全源最短路尝试加入负权边看是否能正常计算