C++如何实现Floyd-Warshall算法_C++求解所有顶点对之间最短路径的动态规划算法-C++-PHP中文网

C++如何实现Floyd-Warshall算法_C++求解所有顶点对之间最短路径的动态规划算法

穿越時空

发布： 2025-11-21 16:50:02

原创

187人浏览过

c++如何实现floyd-warshall算法_c++求解所有顶点对之间最短路径的动态规划算法

弗洛伊德-沃舍尔（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 算法求解所有顶点对之间的最短路径：

GPTKit

一个AI文本生成检测工具

108

查看详情

#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 时同步记录前驱节点。