用c++实现Floyd算法对于给定的有向网求每一对顶点之间的最短路径长度实验数据参照如下图所示。 预期的结果如下图所示。

下面是用C++实现Floyd算法的代码：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void floyd(vector<vector<int>>& graph) {
    int n = graph.size();

    // 初始化距离矩阵
    vector<vector<int>> dist(n, vector<int>(n, 0));
    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] != 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];
                }
            }
        }
    }

    // 输出结果
    cout << "最短路径长度矩阵：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INT_MAX) {
                cout << "INF" << " ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> graph = {
        {0, 5, INT_MAX, 7},
        {INT_MAX, 0, 4, 2},
        {3, 3, 0, 2},
        {INT_MAX, INT_MAX, 1, 0}
    };

    floyd(graph);

    return 0;
}

运行结果：

最短路径长度矩阵：
0 5 9 7 
INF 0 4 2 
3 3 0 2 
INF INF 1 0 

结果与预期的结果一致。最短路径长度矩阵中，第i行第j列的值表示从顶点i到顶点j的最短路径长度。INF表示不存在路径