Floyd算法通过动态规划求解所有顶点对间最短路径，核心是三重循环松弛操作，时间复杂度O(n³)，适用于小规模图且可处理负权边。
在C++中实现Floyd算法（也称Floyd-Warshall算法）用于求解图中所有顶点对之间的最短路径。该算法适用于带权有向图或无向图，能处理负权边（但不能有负权环）。核心思想是动态规划，通过中间节点逐步更新最短路径。
算法基本原理
Floyd算法基于这样一个事实：如果从顶点i到j的最短路径经过某个中间顶点k，那么这条路径可以拆分为i到k和k到j的两段最短路径。通过枚举所有可能的中间点k，不断松弛任意两点间的距离。
设dist[i][j]表示从顶点i到j的当前最短距离，初始时为图的邻接矩阵。算法进行如下更新：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
立即学习“C++免费学习笔记（深入）”；
实现步骤
以下是具体的实现流程：
- 初始化一个二维数组dist，大小为n×n（n为顶点数），表示任意两点间的距离
- 若i==j，则dist[i][j]为0；若i与j之间有边，则赋值为对应权重；否则设为一个极大值（如INT_MAX/2）
- 三重循环：外层枚举中间点k，内层枚举起点i和终点j，尝试通过k更新i到j的距离
- 最终dist[i][j]即为i到j的最短路径长度
C++代码示例
下面是一个完整的C++实现：
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
const int INF = INT_MAX / 2; // 防止加法溢出
void floyd(vector<vector<int>>& dist) {
int n = dist.size();
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] != INF && dist[k][j] != INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
// 输出结果
cout << "最短路径矩阵：" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == INF)
cout << "INF ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
int main() {
int n = 4;
vector<vector<int>> graph = {
{0, 3, INF, 7},
{8, 0, 2, INF},
{5, INF, 0, 1},
{2, INF, INF, 0}
};
floyd(graph);
return 0;
}
注意事项
使用Floyd算法时需注意以下几点：
- INF值不宜取INT_MAX，避免后续加法导致整数溢出，建议用INT_MAX/2
- 算法时间复杂度为O(n³)，适合顶点数较少的图（一般n ≤ 500）
- 空间复杂度为O(n²)，需要存储整个距离矩阵
- 若需记录路径，可额外维护一个parent[i][j]数组，在更新距离时同步更新前驱节点
