floyd最短路径算法C++

Floyd-Warshall算法是一种动态规划的方法，用于求解有向图或多边形图中任意两点之间的最短路径。在C++中，这个算法通过迭代更新所有节点对的距离来找到网络中的最短路径。

以下是基本的Floyd-Warshall算法的C++实现：

#include <vector>
#include <limits>

// 定义邻接矩阵表示图
typedef std::vector<std::vector<int>> Graph;

void floydWarshall(Graph& graph) {
    int n = graph.size(); // 图的节点数
    for (int k = 0; k < n; ++k) { // 对于每个中间节点k
        for (int i = 0; i < n; ++i) { // 对于起点i
            for (int j = 0; j < n; ++j) { // 对于终点j
                if (graph[i][k] + graph[k][j] < graph[i][j]) { // 如果经过k比直接走更短
                    graph[i][j] = graph[i][k] + graph[k][j]; // 更新最短路径
                }
            }
        }
    }
}

// 示例：
Graph graph({{0, 4, 0, 0},
              {2, 0, 1, 5},
              {0, 1, 0, 3},
              {0, 0, 6, 0}}); // 矩阵元素代表边的权重
floydWarshall(graph);

在这个例子中，`graph[i][j]`存储了从节点i到节点j的原始权重，而`graph[i][j] = graph[i][k] + graph[k][j]`表示发现了一个新的最短路径。