考研笔记

板子：Prim 与 Dijkstra

★ 级：逐轮填表的手算是重点，代码认得就行。两个算法的代码几乎一样：每轮选一个「最近」的顶点加入集合，再用它去更新其他顶点。唯一的区别在更新那一行：Prim 比较的是这一条边，Dijkstra 比较的是从源点累计的距离。

代码

int Prim(MGraph &G, int parent[]) {          // 从顶点 0 开始；返回 MST 的总权值，parent[v] 是 v 在树上的双亲
    int n = G.numVertices, lowcost[MAXV];    // lowcost[v]：v 到当前这棵树的最短边
    bool inTree[MAXV];
    for (int v = 0; v < n; v++) {
        lowcost[v] = G.Edge[0][v];
        parent[v] = 0;
        inTree[v] = false;
    }
    inTree[0] = true;
    parent[0] = -1;
    int sum = 0;
    for (int k = 1; k < n; k++) {            // 每轮加入一个顶点，一共 n-1 轮
        int u = -1;
        for (int v = 0; v < n; v++)          // 选出离树最近的顶点 u
            if (!inTree[v] && (u == -1 || lowcost[v] < lowcost[u])) u = v;
        if (lowcost[u] == INF) return -1;    // 最近的也是 INF：图不连通
        inTree[u] = true;
        sum += lowcost[u];
        for (int v = 0; v < n; v++)          // 用 u 更新其他顶点到树的距离
            if (!inTree[v] && G.Edge[u][v] < lowcost[v]) {   // Prim：只比较 u-v 这一条边
                lowcost[v] = G.Edge[u][v];
                parent[v] = u;
            }
    }
    return sum;
}
 
void Dijkstra(MGraph &G, int s, int dist[], int path[]) {   // 从 s 出发；path[v] 是最短路上 v 的前一个顶点
    int n = G.numVertices;
    bool done[MAXV];                         // done[v]：v 的最短路已经确定（已并入集合 S）
    for (int v = 0; v < n; v++) {
        dist[v] = G.Edge[s][v];
        path[v] = (v != s && G.Edge[s][v] < INF) ? s : -1;
        done[v] = false;
    }
    dist[s] = 0;
    done[s] = true;
    for (int k = 1; k < n; k++) {            // 每轮确定一个顶点，最多 n-1 轮
        int u = -1;
        for (int v = 0; v < n; v++)          // 选出 dist 最小、还没确定的顶点 u
            if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (dist[u] == INF) break;           // 剩下的顶点都到不了
        done[u] = true;
        for (int v = 0; v < n; v++)          // 以 u 为中转，更新其他顶点
            if (!done[v] && dist[u] + G.Edge[u][v] < dist[v]) {   // Dijkstra：比较从 s 累计的距离
                dist[v] = dist[u] + G.Edge[u][v];
                path[v] = u;
            }
    }
}

INF 定义在 Floyd 那一篇里：#define INF 0x3f3f3f3f。矩阵是带权矩阵，没有边存 INF，对角线存 0。

复杂度：两个都是时间 ，空间 。

两个算法对照

PrimDijkstra
数组含义lowcost[v]： 到当前这棵树的最短边dist[v]：源点到 的当前最短距离
更新条件G.Edge[u][v] < lowcost[v]dist[u] + G.Edge[u][v] < dist[v]
适用带权无向图带权有向图、无向图，边权不能为负

关键边界

位置为什么
每轮只在「还没加入」的顶点里选已经加入的顶点不能再选，也不能再更新
选出来的是 INFPrim 说明图不连通，没有生成树；Dijkstra 说明剩下的顶点都到不了
dist[u] + G.Edge[u][v] 不会溢出dist[u] < INF，边权最大是 INF，两者相加小于 INF，没超出 int 的范围
path、parent 存前驱输出路径的写法和 BFS 最短路 的 printPath 一样

易错点

  • Dijkstra 遇到负权边会出错：已经确定的顶点不会再被更新，后面出现的负权边可能把它改得更小。
  • 手算 Dijkstra 要按教材表 6.2 逐轮填 dist[] 和路径，这是标准的答题格式。见 6.4.1 Dijkstra 算法。
  • 用堆优化的 Dijkstra 时间更好，但考研不考，手算题也不按它来。

链接

反向链接