对于c++中Floyd算法的总结和举例

Floyd算法，也称为插点法，是一种用于求解任意两点之间最短路径的算法，它的时间复杂度为O(n^3)，适用于稠密图。

具体的实现步骤如下：
1. 初始化一个n*n的二维数组D，其中D[i][j]表示i到j的最短路径长度。
2. 对D进行初始化，若i和j之间有边，则D[i][j]为边的权值，否则D[i][j]为无穷大。
3. 三重循环遍历D，通过比较D[i][j]和D[i][k]+D[k][j]的大小，不断更新D[i][j]的值。

以下是一个使用Floyd算法求解最短路径问题的C++代码示例：

// n为顶点数，graph为邻接矩阵
void floyd(int n, int graph[][MAX]) {
    int D[MAX][MAX];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            D[i][j] = graph[i][j];
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
}

例如，对于下面这个图：

    6   1
 A------>B
 |      /|\
 |  3 / | \ 2
 |   /  |  \
 |  /   | 4 \
 v /    v   v
 C<------D---->E
      5      1

邻接矩阵为：

  A  B  C  D  E
A 0  1  6  ∞  ∞
B ∞  0  ∞  3  2
C ∞  ∞  0  5  ∞
D ∞  ∞  ∞  0  1
E ∞  ∞  ∞  ∞  0

使用Floyd算法求解最短路径后，得到的邻接矩阵为：

  A  B  C  D  E
A 0  1  4  7  3
B ∞  0  ∞  3  2
C ∞  ∞  0  5  6
D ∞  ∞  ∞  0  1
E ∞  ∞  ∞  ∞  0

其中，D[i][j]表示从顶点i到顶点j的最短路径长度。例如，D[A][D]的值为7，表示从A到D的最短路径长度为7。