floyd算法求最短路径c++

以下是使用C++实现Floyd算法求解最短路径的示例代码：

#include <iostream>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f; // 表示无穷大
const int MAXN = 100;      // 最大顶点数

int G[MAXN][MAXN]; // 存储图的邻接矩阵
int dist[MAXN][MAXN]; // 存储最短路径的长度
int path[MAXN][MAXN]; // 存储最短路径上的顶点

void floyd(int n) {
    // 初始化dist和path数组
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dist[i][j] = G[i][j];
            path[i][j] = -1;
        }
    }

    // Floyd算法核心代码
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

// 输出从i到j的最短路径
void print_path(int i, int j) {
    if (path[i][j] == -1) {
        cout << j << " ";
    } else {
        int k = path[i][j];
        print_path(i, k);
        print_path(k, j);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    // 初始化邻接矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                G[i][j] = 0;
            } else {
                G[i][j] = INF;
            }
        }
    }

    // 读入边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u][v] = w;
    }

    floyd(n);

    // 输出每对顶点之间的最短路径长度和路径
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << "From " << i << " to " << j << ": " << dist[i][j] << ", path: ";
            print_path(i, j);
            cout << endl;
        }
    }

    return 0;
}

在上述代码中，`G[i][j]`表示顶点i到顶点j的边权值，如果i和j之间没有边，则`G[i][j]`应该设置为一个较大的数（本示例中设为INF）。

`dist[i][j]`表示从顶点i到顶点j的最短路径长度，`path[i][j]`表示从顶点i到顶点j的最短路径上的顶点。

在`floyd()`函数中，先用邻接矩阵初始化`dist`和`path`数组，然后按照Floyd算法的步骤进行计算。在计算过程中，如果发现从顶点i到顶点j经过顶点k的路径长度更短，则更新`dist[i][j]`和`path[i][j]`的值。

在输出最短路径时，可以使用递归函数`print_path()`来输出从i到j的路径。如果`path[i][j]`为-1，则表示从i到j直接有一条边，输出j即可；否则，先输出从i到k的路径，再输出从k到j的路径即可。

最后，遍历每对顶点之间的最短路径长度和路径，输出结果即可。