求t(R)的矩阵warshall算法用C++实现

Warshall算法是一种用于求解加权图中所有顶点对之间的最短路径的算法。该算法的核心思想是将图中所有顶点对之间的距离都更新为所有从源顶点到该顶点的最短路径加上从该顶点到目标顶点的权重。

以下是使用C++实现Warshall算法的代码，可以求解给定图的t(R)矩阵。

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

using namespace std;

void warshall(vector<vector<int>>& graph, vector<vector<int>>& tR) {
    int n = graph.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tR[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 (graph[i][k] + graph[k][j] < tR[i][j]) { // 如果从顶点k到顶点j的最短路径更短，则更新tR[i][j]
                    tR[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // 图的邻接矩阵表示
    vector<vector<int>> tR(graph.size(), vector<int>(graph.size(), INT_MAX)); // t(R)矩阵，初始化为无穷大
    warshall(graph, tR); // 求解t(R)矩阵并输出结果
    return 0;
}

在这个代码中，我们首先将图中所有顶点对之间的距离初始化为原来的值。然后使用三层循环，将tR矩阵中的每个元素都更新为从源顶点到该顶点的最短路径加上从该顶点到目标顶点的权重。最后，输出的结果即为t(R)矩阵。需要注意的是，我们使用了向量和数组来表示图和t(R)矩阵，这些类型是C++标准库中的类型。在上述代码中，我们假设图的邻接矩阵表示，即图中的每个元素表示两个顶点之间的权重。