求t(R)的warshall算法（C++）

Warshall算法，也称为Floyd-Warshall算法，是一种用于求解所有节点对之间的最短路径的动态规划方法，适用于图的有向或无向、加权或非加权的情况。在C++中，我们可以按照以下步骤编写该算法：

#include <vector>
using namespace std;

// 定义邻接矩阵来表示图
vector<vector<int>> graph(int vertices, vector<pair<int, int>>& edges) {
    vector<vector<int>> adj(vertices, vector<int>(vertices, INT_MAX)); // 初始化为无穷大
    for (auto& edge : edges) {
        adj[edge.first][edge.second] = edge.second; // 如果存在边，则更新对应距离为权重
    }
    return adj;
}

// Warshall算法核心部分
void warshallFloyd(vector<vector<int>>& graph) {
    int n = graph.size();
    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] != INT_MAX && graph[k][j] != INT_MAX)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

// 示例
int main() {
    int vertices;
    vector<pair<int, int>> edges;
    cout << "Enter number of vertices and edges: ";
    cin >> vertices >> vertices * vertices;
    cout << "Enter edges in the form (source, destination, weight):" << endl;
    for (int i = 0; i < vertices * vertices; i++) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
        edges.push_back({src, dest});
    }
    
    vector<vector<int>> adj = graph(vertices, edges);
    warshallFloyd(adj);

    cout << "\nShortest path matrix after applying Floyd-Warshall algorithm:\n";
    for (auto row : adj) {
        for (int distance : row) {
            cout << distance << " ";
        }
        cout << endl;
    }

    return 0;
}

在这个例子中，我们首先输入图的顶点数和边信息，然后通过用户输入创建邻接矩阵。接着调用`warshallFloyd`函数计算最短路径，并最终打印出结果。