void Floyed(MatGraph g)

Floyd 算法是一种用于寻找加权图中最短路径的算法，它可以处理有向或无向图，有负权边（但不能有负权环），并且使用动态规划的思想。

在 Floyd 算法中，我们首先初始化一个二维的距离矩阵，其中距离矩阵中的每个元素 d(i,j) 表示从顶点 i 到顶点 j 的最短路径长度。

接下来，我们使用三重循环，枚举每对顶点 (i, j)，以及中间经过的顶点 k，计算出从 i 到 j 经过 k 的路径长度是否小于不经过 k 的路径长度，如果是，则更新距离矩阵中的值。

最后，距离矩阵中的元素就是所有顶点对之间的最短路径长度。

下面是 Floyd 算法的 C++ 代码实现，假设输入的图用邻接矩阵表示：

const int INF = 0x3f3f3f3f;

void Floyd(MatGraph g) {
    int n = g.n;
    int d[n][n];
    memcpy(d, g.edges, sizeof(d)); // 初始化距离矩阵为邻接矩阵
    for (int k = 0; k < n; k++) { // 枚举中间经过的顶点
        for (int i = 0; i < n; i++) { // 枚举起点
            for (int j = 0; j < n; j++) { // 枚举终点
                if (d[i][k] < INF && d[k][j] < INF) // 避免溢出
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    // 输出距离矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][j] == INF)
                cout << "INF ";
            else
                cout << d[i][j] << " ";
        }
        cout << endl;
    }
}

该代码的时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。