Floyd算法详解（C++实现多源最短路径）

算法核心思想

Floyd算法的核心思想是：逐步尝试通过中间节点来优化任意两点之间的路径。

假设我们有一个图 G，包含 n 个顶点。我们用一个二维数组 dist[i][j] 表示从顶点 i 到顶点 j 的最短距离。

算法通过三重循环，依次考虑每个顶点 k 作为“中转站”，检查是否可以通过 k 来缩短 i 到 j 的路径：

if (dist[i][k] + dist[k][j] < dist[i][j]) {    dist[i][j] = dist[i][k] + dist[k][j];}

C++ 实现步骤

下面我们用 C++ 一步步实现 Floyd 算法。

1. 初始化距离矩阵

- 如果 i == j，距离为 0；

- 如果 i 和 j 之间有直接边，填入边的权重；

- 否则，设为一个很大的数（表示不可达，通常用 INT_MAX/2 避免溢出）。

2. 三重循环更新最短路径

外层循环枚举中间点 k，内层循环枚举起点 i 和终点 j。

3. 输出结果

最终的 dist 矩阵即为所有点对之间的最短路径。

完整C++代码示例

#include <iostream>#include <vector>#include <climits>#include <algorithm>using namespace std;const int INF = INT_MAX / 2; // 防止加法溢出void floydWarshall(vector<vector<int>>& dist, int n) {    // 三重循环：k 为中间点，i 为起点，j 为终点    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]);                }            }        }    }}int main() {    int n = 4; // 顶点数量    // 初始化距离矩阵    vector<vector<int>> dist = {        {0,   3,   INF, 7},        {8,   0,   2,   INF},        {5,   INF, 0,   1},        {2,   INF, INF, 0}    };    cout << "原始距离矩阵：\n";    for (auto& row : dist) {        for (int d : row) {            if (d == INF) cout << "INF ";            else cout << d << "   ";        }        cout << "\n";    }    floydWarshall(dist, n);    cout << "\nFloyd算法后的最短路径矩阵：\n";    for (auto& row : dist) {        for (int d : row) {            if (d == INF) cout << "INF ";            else cout << d << "   ";        }        cout << "\n";    }    return 0;}

算法优缺点

• 优点：代码简洁，能一次性求出所有点对的最短路径；支持负权边。
• 缺点：时间复杂度较高（O(n³)），不适合大规模图；无法处理存在负权环的图。

应用场景

Floyd算法常用于网络路由、交通规划、社交网络分析等需要计算多源最短路径的场景。例如，在城市导航系统中，若需预计算任意两个地点之间的最短行车时间，Floyd算法是一个可行的选择（当城市规模不大时）。

总结

通过本教程，你应该已经掌握了Floyd算法的基本原理和 C++ 实现方法。记住，理解算法背后的动态规划思想比死记代码更重要。多动手写几遍代码，尝试修改图的结构，观察输出变化，你会对这个经典的图论算法有更深的理解。

希望这篇教程对你有帮助！如果你正在学习C++最短路径相关的内容，不妨也尝试 Dijkstra 或 Bellman-Ford 算法，它们分别适用于单源最短路径的不同场景。