弗洛伊德-沃舍尔（Floyd-Warshall）算法是一种经典的动态规划算法，用于求解有向或无向图中所有顶点对之间的最短路径。它适用于带权图，支持负权边，但不支持包含负权环的图。C++实现该算法简单高效，适合稠密图。
算法基本思想
Floyd-Warshall 的核心是动态规划：逐步尝试通过中间节点优化任意两点间的距离。设 dist[i][j] 表示从顶点 i 到 j 的最短距离。初始时，dist[i][j] 为图的邻接矩阵值。然后枚举每一个可能的中间点 k，检查是否可以通过 k 缩短 i 到 j 的路径：
状态转移方程： dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
C++ 实现代码
以下是一个完整的 C++ 示例，演示如何使用 Floyd-Warshall 算法求解所有顶点对之间的最短路径：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int INF = INT\_MAX / 2; // 防止加法溢出
void floydWarshall(vector<vector<int>>& dist) {
int n = dist.size();
// 动态规划：枚举中间点 k
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 << "所有顶点对之间的最短距离：\n";
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 << "\n";
}
}
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}
};
floydWarshall(graph);
return 0;
}
关键细节说明
• 使用 INT_MAX / 2 而不是 INT_MAX 是为了避免在加法中发生整数溢出。
• 图以邻接矩阵形式表示，INF 表示两点间无直接边。
• 三重循环中，k 必须放在最外层，确保每次只引入一个新中间节点，符合动态规划顺序。
• 若需记录具体路径，可额外维护一个 parent[i][j] 数组，在更新 dist 时同步记录前驱节点。
时间与空间复杂度
• 时间复杂度：O(n³)，三重循环。
• 空间复杂度：O(n²)，存储距离矩阵。
适合顶点数不多（如 n ≤ 200）的场景，尤其适用于稠密图。
基本上就这些。Floyd-Warshall 实现简洁，理解其状态转移逻辑是关键。对于稀疏图，可以考虑 Johnson 算法替代。
立即学习“C++免费学习笔记（深入）”；
