c++实现Floyd算法程序

Floyd算法，也称为Floyd-Warshall算法，是一种用于寻找所有最短路径的动态规划方法，常用于解决图中的最短路径问题。在C++中实现Floyd算法，通常会用邻接矩阵来表示图。以下是一个简单的C++代码示例：

#include <vector>
#include <climits>

void floydWarshall(std::vector<std::vector<int>>& graph, int numVertices) {
    // 初始化距离矩阵，所有顶点间的初始距离为无穷大，除了对角线为0（从顶点到自身的距离）
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            graph[i][j] = graph[i][j] == INT_MAX ? 0 : graph[i][j];
            for (int k = 0; k < numVertices; ++k) {
                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX)
                    graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

// 示例图（这里仅为简化说明，实际使用应替换为实际的邻接矩阵）
std::vector<std::vector<int>> createGraph(int vertices) {
    std::vector<std::vector<int>> graph(vertices, std::vector<int>(vertices, INT_MAX));
    // 填充图的边和权重（这里仅作为示例，具体根据实际需求填充）
    graph = graph = 1;
    graph[2] = graph = 2;
    // 更多边和权重...
    return graph;
}

int main() {
    int numVertices = 3; // 例如，如果你有三个顶点
    std::vector<std::vector<int>> graph = createGraph(numVertices);
    floydWarshall(graph, numVertices);

    // 打印出经过Floyd算法更新后的最短路径矩阵
    for (const auto& row : graph) {
        for (const int dist : row) {
            if (dist != INT_MAX) {
                std::cout << dist << " ";
            } else {
                std::cout << "∞ ";
            }
        }
        std::cout << std::endl;
    }

    return 0;
}