使用Floyd算法求解任意两结点的最短路径问题c++

Floyd算法是一种用于求解任意两结点最短路径的动态规划算法。下面是使用C++实现Floyd算法求解最短路径问题的代码示例：

#include <iostream>
#include <vector>

#define INF 99999

// 使用Floyd算法求解任意两结点的最短路径
void floydWarshall(std::vector<std::vector<int>>& graph, int n) {
    std::vector<std::vector<int>> dist(n, std::vector<int>(n));

    // 初始化距离矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[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] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 打印最短路径
    std::cout << "最短路径矩阵：" << std::endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                std::cout << "INF ";
            } else {
                std::cout << dist[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    int n = 4;  // 结点数量

    std::vector<std::vector<int>> graph = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph, n);

    return 0;
}

以上代码中，`graph` 是一个邻接矩阵表示的图，`INF` 表示两个结点之间不存在直接连接。`floydWarshall` 函数使用Floyd算法计算任意两结点的最短路径，并将结果存储在 `dist` 矩阵中。最后，我们打印出最短路径矩阵。

在 `main` 函数中，我们测试了一个示例图，并输出了最短路径矩阵。

希望这个代码示例能够帮助到你！