【图论算法】Floyd-Warshall多源最短路算法

一、算法简介Floyd-Warshall弗洛伊德算法是图论中经典的多源最短路径算法区别于Dijkstra单源最短路算法该算法可以一次性求出图中任意两个顶点之间的最短距离。核心特点适用场景无负权环的有向图/无向图支持负权边时间复杂度$$O(n^3)$$n为顶点数适合小规模图顶点数≤100优势代码极简、无需多次迭代一次计算得到所有点对最短路劣势时间复杂度较高不适合大规模图二、算法核心原理Floyd算法的核心思想是动态规划枚举中间节点k判断 i→k→j 的路径是否比 i→j 直接路径更短不断松弛更新最短距离。状态转移公式$$dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])$$三层循环释义最外层k枚举所有可中转的中间顶点中层i枚举起点内层j枚举终点三、完整可运行代码本次代码实现4个顶点的有向图手动构建边权求解所有顶点对的最短路径兼容超大值无穷大处理可直接复制编译运行。#include stdio.h #include limits.h #define MAX_V 100 // 最大顶点数 #define INF (INT_MAX / 2) // 无穷大避免相加溢出 int graph[MAX_V][MAX_V]; // 原图邻接矩阵 int dist[MAX_V][MAX_V]; // 存储最终最短路距离矩阵 // Floyd-Warshall核心算法 void floyd_warshall(int n) { // 1. 初始化距离矩阵复制原图权值 for (int i 0; i n; i) { for (int j 0; j n; j) { dist[i][j] graph[i][j]; } } // 2. 三重循环松弛更新最短路 for (int k 0; k n; k) { // 中间节点 for (int i 0; i n; i) { // 起点 for (int j 0; j n; j) { // 终点 // 中转路径更短则更新 if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } } int main(void) { int n 4; // 顶点数量 // 初始化邻接矩阵自身到自身距离为0其余为无穷大 for (int i 0; i n; i) { for (int j 0; j n; j) { graph[i][j] (i j) ? 0 : INF; } } // 手动赋值图的边权 graph[0][1] 5; graph[0][3] 10; graph[1][2] 3; graph[2][3] 1; // 执行Floyd算法 floyd_warshall(n); // 打印所有顶点对最短距离 printf(所有顶点对最短距离矩阵\n); for (int i 0; i n; i) { for (int j 0; j n; j) { if (dist[i][j] INF) printf(∞\t); else printf(%d\t, dist[i][j]); } printf(\n); } return 0; }四、代码细节详解1. 无穷大INF定义代码中使用INT_MAX / 2作为无穷大而非直接用INT_MAX目的是防止两个无穷大数值相加导致int溢出报错是Floyd算法的经典避坑写法。2. 邻接矩阵初始化规则顶点自身到自身距离为 0无直接相连的两个顶点距离为 INF无穷大有直接边连接的顶点赋值为对应边权3. 松弛操作核心通过中间节点k不断优化i到j的路径如果i→k→j的路径长度小于i→j直达路径就更新最短距离。三层循环顺序固定不可调换k、i、j顺序。五、测试用例图结构本次测试构建4节点有向图边关系如下0 → 1 权值 50 → 3 权值 101 → 2 权值 32 → 3 权值 1最优路径举例0→1→2→3 总权值 5319比直达0→310更短算法会自动优化该路径。六、运行结果展示编译运行代码后输出结果如下所有顶点对最短距离矩阵 0 5 8 9 ∞ 0 3 4 ∞ ∞ 0 1 ∞ ∞ ∞ 0结果解析第1行顶点0出发0到15、0到28、0到39优化后最短路径第2行顶点1出发1到23、1到341→2→3第3行顶点2出发2到31无连通路径显示 ∞七、常见问题与注意事项溢出问题严禁直接使用INT_MAX作为INF相加会造成整型溢出负权环判断若最终dist[i][i] 0说明图中存在负权环适用范围顶点数超过100不建议使用推荐Dijkstra、SPFA算法循环顺序必须先枚举中间节点k再枚举起点i、终点j八、总结Floyd-Warshall算法凭借极简的代码逻辑成为小规模图多源最短路的首选算法。虽然时间复杂度较高但无需复杂的数据结构、无需遍历邻接表仅通过邻接矩阵三重循环即可实现非常适合算法入门、课程作业、小规模场景使用。往期推荐Dijkstra单源最短路算法、SPFA负权最短路算法、最小生成树Kruskal算法