弗洛伊德最短路径c++

以下是使用C++实现弗洛伊德最短路径算法的示例代码：

#include <iostream>
#include <climits>

#define V 4 // 图中顶点的数量

void floydWarshall(int graph[V][V]) {
    int dist[V][V];

    // 初始化距离矩阵为图中的边权值
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // 通过中间顶点逐步更新距离矩阵
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // 如果顶点k作为中间顶点可以使得路径更短，则更新距离矩阵
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最短路径矩阵
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INT_MAX) {
                std::cout << "INF ";
            } else {
                std::cout << dist[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    int graph[V][V] = {
        {0, 5, INT_MAX, 10},
        {INT_MAX, 0, 3, INT_MAX},
        {INT_MAX, INT_MAX, 0, 1},
        {INT_MAX, INT_MAX, INT_MAX, 0}
    };

    floydWarshall(graph);

    return 0;
}

这段代码实现了弗洛伊德最短路径算法，通过一个三重循环逐步更新距离矩阵，最终输出每对顶点之间的最短距离。在示例中，我们使用一个4个顶点的图来演示算法的工作原理。