弗洛伊德算法的核心思想是通过逐步引入中间顶点，不断更新任意两个顶点之间的最短路径长度。它的逻辑非常直观，对于图中的每一对顶点i和j，尝试判断是否存在一个中间顶点k，使得从i到k再到j的路径长度比当前记录的i到j的直接路径更短，如果是就更新最短路径值。
弗洛伊德算法核心原理
算法的执行过程可以分为三个关键步骤：
- 初始化距离矩阵，将图中直接相连的边的权值作为初始距离，不相连的边设为无穷大，顶点到自身的距离设为0
- 三重循环遍历所有顶点作为中间顶点k，再遍历所有顶点对i和j，判断经过k的路径是否更短
- 循环结束后，距离矩阵中存储的就是所有点对之间的最短路径长度
需要注意的是，弗洛伊德算法可以处理负权边，但如果图中存在负权环，算法会得出错误结果，因为负权环会让路径长度无限减小。
C++实现完整代码
下面的代码实现了带权有向图的弗洛伊德算法，包含距离计算和基础的结果输出：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 定义无穷大值，表示两个顶点之间没有直接连通的路径
const int INF = INT_MAX / 2;
// 弗洛伊德算法实现函数
// 参数graph是初始的邻接矩阵，vertex_num是顶点数量
void floydWarshall(vector<vector<int>>& graph, int vertex_num) {
// 距离矩阵，初始化为输入的邻接矩阵
vector<vector<int>> dist = graph;
// 核心三重循环，k是中间顶点
for (int k = 0; k < vertex_num; k++) {
for (int i = 0; i < vertex_num; i++) {
// 如果i到k的路径已经是无穷大，就不需要再判断后续路径
if (dist[i][k] == INF) continue;
for (int j = 0; j < vertex_num; j++) {
// 判断经过k的路径是否更短
if (dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 输出所有点对的最短路径结果
cout << "所有点对的最短路径长度如下：" << endl;
for (int i = 0; i < vertex_num; i++) {
for (int j = 0; j < vertex_num; j++) {
if (dist[i][j] == INF) {
cout << "INF" << "t";
} else {
cout << dist[i][j] << "t";
}
}
cout << endl;
}
}
int main() {
// 初始化图，这里以4个顶点为例
int vertex_num = 4;
vector<vector<int>> graph(vertex_num, vector<int>(vertex_num, INF));
// 设置顶点到自身的距离为0
for (int i = 0; i < vertex_num; i++) {
graph[i][i] = 0;
}
// 添加图中的边和权值，这里是无向图的示例，有向图可以只设置单向
graph[0][1] = 3;
graph[0][2] = 8;
graph[0][3] = 5;
graph[1][2] = 2;
graph[2][3] = 1;
// 无向图需要补充反向边
graph[1][0] = 3;
graph[2][0] = 8;
graph[3][0] = 5;
graph[2][1] = 2;
graph[3][2] = 1;
// 调用弗洛伊德算法
floydWarshall(graph, vertex_num);
return 0;
}
代码逻辑说明
上述代码中，首先定义了INF常量表示无穷大，避免直接使用INT_MAX导致加法溢出。初始化邻接矩阵时，先所有值设为无穷大，再把顶点到自身的距离设为0，之后添加实际的边权值。
核心的floydWarshall函数中，先复制一份邻接矩阵作为距离矩阵，然后通过三重循环更新最短路径。外层循环遍历中间顶点k，内层两层循环遍历所有顶点对i和j，判断经过k的路径是否更短。最后输出结果时，遇到无穷大值就输出INF标识。
算法特性与注意事项
弗洛伊德算法的时间复杂度是O(n³)，其中n是图的顶点数量，因此更适合顶点数量较少的场景。如果顶点数量过多，算法执行效率会明显下降。
在实际开发中，如果需要同时记录最短路径的具体路线，可以额外维护一个前驱节点矩阵，在更新最短路径时同步更新前驱节点，最后通过回溯前驱节点得到完整路径。
另外要注意输入图的合法性，如果存在负权环，算法输出的结果没有实际意义，需要在算法执行前先判断图中是否存在负权环。