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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-11-21

浏览次数：次

返回列表

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 算法求解所有顶点对之间的最短路径：

CA.LA

第一款时尚产品在线设计平台，服装设计系统

94 查看详情 CA.LA

#include iostream>
#include
#include
using namespace std;

const int INF = INT\_MAX / 2; // 防止加法溢出

void floydWarshall(vector>& dist) {
int n = dist.size();

// 动态规划：枚举中间点 k
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]);
}
}
}
}

// 输出结果
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> 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 时同步记录前驱节点。