c++实现warshal算法

沃拉斯特定理（Warshall's Algorithm），也称为Floyd-Warshall算法，是一种用于求解有向图中最短路径的动态规划方法。在C++中实现沃拉斯特定理，主要步骤如下：

1. 定义一个二维数组`dist`，其中`dist[i][j]`表示从顶点i到顶点j的最短路径长度。初始化所有对角线元素为0（因为从一个顶点到自身距离是0），其他元素为无穷大（表示不存在连接）。

int n; // 图的顶点数
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

2. 使用三层嵌套循环，对于每对顶点(i, j)，检查是否存在第三顶点k，使得通过k可以得到比直接从i到j更短的距离。更新`dist[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][j] > dist[i][k] + dist[k][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

3. 最终，`dist[i][j]`将存储从顶点i到顶点j的最短路径长度。

沃拉斯特定理适用于处理包含负权重边的有向图，但它不是图形数据结构的一部分，所以在实际应用中，可能需要配合`std::vector`等容器以及自定义图的表示。