Dijkstra最短路算法

解决单源最短路径问题常用Dijkstra算法，用于计算一个顶点到其他所有顶点的最短路径

算法思想——以起点为中心，逐层向外扩展，每次都会取一个最近点继续扩展，直到取完为止。

Ps.Dijkstra算法要求图中不能出现负权边。

算法步骤——

1、创建数组dist，dist[v]表示从源点s出发到顶点v的距离。初始化 到每个顶点的距离 dist[v] 为无穷大inf，源点M的dist[M]设置为0。

    dist[v] = inf;

    dist[M] = 0;

2、此时dist[M]最小，设置dist[M]为已确定的最短路径。接着从M点出发，更新相邻点的dist。

    dist[X] = max(dist[M] + MX, dist[X]);    //10

    dist[W] = max(dist[M] + MW, dist[W]);    //5

    dist[E] = max(dist[M] + ME, dist[E]);     //8

3、更新完后，剩下的点中dist[W]最小，设置dist[W]为已确定路径。接着从W点出发，更新相邻点的dist。

4、更新完后，剩下的点中dist[E]最小，设置dist[E]为已确定路径。接着从E点出发，更新相邻点的dist。

5、更新完后，剩下的点中dist[X]最小，设置dist[X]为已确定路径。接着从X点出发，更新相邻点的dist。

6、更新完后，剩下的点中dist[D]最小，设置dist[D]为已确定路径。接着从W点出发，不存在其它剩下的点了。

参考代码——

const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n;
void mapinit() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int w) {  // 插入带权有向边
    e[eid].v = v;
    e[eid].w = w;
    e[eid].next = p[u];
    p[u] = eid++;
}
void insert2(int u, int v, int w) {  // 插入带权双向边
    insert(u, v, w);
    insert(v, u, w);
}

int dist[MAX_N];  // 存储单源最短路的结果
bool vst[MAX_N];  // 标记每个顶点是否在集合 U 中（是否已确定）
bool dijkstra(int s) {
    memset(vst, 0, sizeof(vst));
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for (int i = 0; i < n; ++i) {
        int v, min_w = inf;  // 记录 dist 最小的顶点编号和 dist 值
        for (int j = 0; j < n; ++j) {
            if (!vst[j] && dist[j] < min_w) {
                min_w = dist[j];
                v = j;
            }
        }
        if (min_w == inf) {  // 没有可用的顶点，算法结束，说明有顶点无法从源点到达
            return false;
        }
        vst[v] = true;  // 将顶点 v 加入集合 U 中
        for (int j = p[v]; j != -1; j = e[j].next) {
            // 如果和 v 相邻的顶点 x 满足 dist[v] + w(v, x) < dist[x] 则更新 dist[x]，这一般被称作“松弛”操作
            int x = e[j].v;
            if (!vst[x] && dist[v] + e[j].w < dist[x]) {
                dist[x] = dist[v] + e[j].w;
            }
        }
    }
    return true;  // 源点可以到达所有顶点，算法正常结束
}

例题：特殊的生成树

给定一张无向图，其中边权都是正数，你需要求出总代价最小的生成树，生成树上的每条边的(u, v)的权值，const(v)是v所在子树的结点数总和。

解法：虽然看起来是一道生成树的题，实际上是一道单源最短路的题目。我们把整棵树的代价加起来，实际上就等于从根结点出发到每个顶点的最短路之和。因此，从每个顶点出发求一遍单源最短路，取其中最短路总和最小的一个顶点作为根，其到所有顶点的单源最短路的总和就是最终答案。

两种次短路——除最短路以外长度最小的路径

第一种：可以重复经过一个点

创建两个数组dist0和dist1，分别代表最短路和次短路的答案。每次更新时需要依次判断是否可以更新最短路和次短路的值。

第二种：不可以重复经过点

枚举两个顶点上的每条边，每次在去掉这条边的剩下的图中计算最短路，取其中最小的一个答案就是最终次短路的答案。