Floyd算法通过动态规划求任意两点间最短路径，核心是三重循环更新距离矩阵：disti = min(disti, disti + distk)，适用于含负权边但无负权环的图。
在C++中实现Floyd最短路径算法，主要是利用动态规划的思想求解图中任意两点之间的最短距离。该算法适用于带权有向或无向图，能处理负权边（但不能有负权环）。
算法基本思想
Floyd算法通过一个三维递推过程逐步更新任意两点间的最短路径。其核心公式为：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
其中 k 是中间节点，i 和 j 是起始和终止节点。算法枚举所有可能的中间节点 k，尝试通过 k 缩短 i 到 j 的路径。
立即学习“C++免费学习笔记（深入）”；
代码实现步骤
以下是完整的C++实现方法：
1. 定义图的大小和初始化距离矩阵
2. 输入边的信息并填充初始距离值
3. 使用三重循环执行Floyd算法
4. 输出任意两点间的最短路径
#include iostream>
#include
#include
using namespace std;
const int INF = INT_MAX / 2; // 防止加法溢出
void floyd(vector
for (int k = 0; k
for (int i = 0; i
for (int j = 0; j
if (dist[i][k] != INF && dist[k][j] != INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
void printDist(const vector
cout
for (int i = 0; i
for (int j = 0; j
if (dist[i][j] == INF)
cout
else
cout
}
cout
}
}
int main() {
int n = 4; // 节点数
vector
// 自身到自身距离为0
for (int i = 0; i
dist[i][i] = 0;
// 添加边：u -> v, 权重 w
dist[0][1] = 3;
dist[0][2] = 6;
dist[1][2] = 4;
dist[1][3] = 4;
dist[2][3] = 8;
floyd(dist, n);
printDist(dist, n);
return 0;
}
关键注意事项
Floyd算法的时间复杂度为 O(n³)，空间复杂度为 O(n²)，适合节点数量不多的图（一般 n ≤ 500）。
使用INT_MAX时要小心溢出问题，建议用一个较大的有限值代替，如 INT_MAX / 2。
若需记录路径而不仅是距离，可额外维护一个 path[i][j] 数组记录中间节点，通过递归回溯输出具体路径。
基本上就这些，实现简单，重点在于初始化和三层循环的顺序。
