考研笔记

板子：Floyd（每对顶点之间的最短路径）

三重循环，中转点 放在最外层：依次允许经过顶点 中转，看 是否比现在的 更短。

代码

#define INF 0x3f3f3f3f                       // 「无穷大」：两个 INF 相加也不会超出 int 的范围
 
void Floyd(MGraph &G, int A[][MAXV], int path[][MAXV]) {   // A：最短路径长度；path：中转点，-1 表示直达
    int n = G.numVertices;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            A[i][j] = G.Edge[i][j];          // 初始值：有边就是边的权值，没有边是 INF，对角线是 0
            path[i][j] = -1;
        }
    for (int k = 0; k < n; k++)              // 中转点 k 必须放在最外层
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (A[i][k] + A[k][j] < A[i][j]) {   // 经过 k 中转更短，就更新
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
}
 
void printFloydPath(int path[][MAXV], int i, int j) {     // 输出 i 到 j 的路径上的中间顶点
    int k = path[i][j];
    if (k == -1) return;                     // i 直接到 j，中间没有顶点
    printFloydPath(path, i, k);              // 先输出 i 到 k 这一段的中间顶点
    printf("%d ", k);
    printFloydPath(path, k, j);              // 再输出 k 到 j 这一段的中间顶点
}

复杂度：时间 ，空间 。

关键边界

位置为什么
k 在最外层这是动态规划的阶段。算 时要用到完整的 ，k 放到里层结果就错了
INF 取 0x3f3f3f3f两个 INF 相加约为 ，没有超出 int 的上限；取 0x7fffffff 的话，相加会溢出变成负数
矩阵初始化带权矩阵：没有边存 INF，对角线存 0。和前面几篇的 0/1 矩阵不一样
path[i][j] = k 存中转点输出路径时递归拆成 和 两段

易错点

  • 允许有负权边，但不允许有负权回路。
  • 手算题常考「写出 、……」：第 步只用第 行、第 列去更新其他格子，第 行、第 列本身不变。见 6.4.1 Floyd 算法。
  • Floyd 也可以用在带权无向图上，把每条无向边看成两条方向相反的有向边。

链接

反向链接