Floyd最短路径算法c++

Floyd-Warshall 算法是一种用于计算图中所有节点对之间最短路径的动态规划方法。在 C++ 中实现这个算法，通常用于解决求解有向或无向图中任意两点间的最短路径问题。以下是算法的主要步骤和一个简单的 C++ 示例：

1. 初始化距离矩阵：对于图中的每条边 (u, v)，如果起点 u 可以通过这条边直接到达终点 v，那么初始的距离矩阵中，d[u][v] 就是这条边的权重；否则，距离为无穷大。

2. 动态更新：对所有的中间节点 k 进行循环（从 0 到 n-1，n 为节点数），检查是否存在这样的情况：d[i][j] > d[i][k] + d[k][j]。如果存在，说明通过 k 中间节点的路径更短，就更新 d[i][j] 的值。

3. 重复步骤2，直到没有更多的路径可以更新，此时得到的 d[][] 中的值就是最终的最短路径。

以下是一个简化的 C++ 代码实现：

#include <vector>
#include <climits>

// 假设 weights 为邻接矩阵，表示图的权重
void floydWarshall(std::vector<std::vector<int>>& weights) {
    int n = weights.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (weights[i][j] > weights[i][k] + weights[k][j]) {
                    weights[i][j] = weights[i][k] + weights[k][j];
                }
            }
        }
    }
}

// 使用示例
std::vector<std::vector<int>> graph = {{0, 1, INT_MAX}, {INT_MAX, 0, 4}, {2, INT_MAX, 0}}; // 用 INT_MAX 表示无穷远
floydWarshall(graph);