生成一份C++floyd模板代码

Floyd算法，也被称为Floyd-Warshall算法，是一个用于求解图中最短路径的经典动态规划方法。在C++中编写这个算法的模板代码通常涉及两个部分：数据结构（如邻接矩阵或邻接表表示图）和算法主体。

以下是使用邻接矩阵表示图并计算所有对之间的最短路径的Floyd算法C++模板代码：

template <typename T>
void floyd_warshall(vector<vector<T>>& graph, int n) {
    // 初始化距离矩阵，假设所有边的初始距离为无穷大
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                graph[i][j] = INT_MAX;
            }
        }
    }

    // 使用二维数组保存已经找到的较短路径
    vector<vector<bool>> path(n, vector<bool>(n, false));

    // 检查所有的中间节点
    for (int k = 0; k < n; ++k) {
        // 对于每一对节点i和j
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // 如果存在通过第三个城市k的更短路径
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    // 更新最短路径，并标记路径已经发现
                    graph[i][j] = graph[i][k] + graph[k][j];
                    path[i][j] = true;
                }
            }
        }
    }

    // 输出或者处理最后得到的最短路径矩阵
    // 根据需要，你可以在这里添加输出或进一步的操作
}

// 使用示例
int main() {
    int numVertices = 5;
    vector<vector<int>> graph(numVertices, vector<int>(numVertices)); // 初始化你的邻接矩阵

    // 填充实际的距离
    graph[0][1] = 1;
    graph[1][2] = 2;
    // ... 其他边的值

    floyd_warshall(graph, numVertices);
    return 0;
}