最短路

• 单源最短路：求源点到汇点的最短路
  • 所有边权为正数
    • 朴素 Dijkstra 算法：适用稠密图 $O(n^2)$
    • 堆优化 Dijkstra 算法：适用稀疏图 $O(m\log n)$
    • $n$ 为点数，$m$ 为边数，稠密图 $m\sim n^2$，稀疏图 $m\sim n$
  • 存在负权边
    • Bellman-Ford 算法：$O(mn)$
    • SPFA 算法：对 BF 算法的优化，平均时间复杂度 $O(m)$，最坏时间复杂度 $O(mn)$
    • 并不是所有情况下都可以用 SPFA 算法（经过不超过 $k$ 条边的最短路）
• 多源汇最短路：任选两个点之间的最短路
  • Floyd 算法：$O(n^3)$

最短路算法难点不在于算法的正确性，考察的侧重点是建图：如何定义点和边 使得成为一个最短路问题。

朴素 Dijkstra 算法

求某个点 $n$ 到 $1$ 号点的最短距离。

• 初始化：dist[1] = 0, dist[i] = +inf，起点的距离为 0，其他点的距离为一个很大的数
• 集合 S 存储当前已经确定最短距离的点（到 $1$ 号点的最短距离）
• 循环 n 次
  • 找到不在 S 中的距离 $1$ 号点最近的点 t（比如第一次就是 $1$ 号点自身）
  • 将其放入 S 集合中
  • 用该点更新其他点的最短距离 dist（更新 t 邻居 j 的最短距离 dist[j]）
  • dist[j] = min(dist[j], dist[t] + w[t][j])
• 每次迭代都可以确定一个点的最短距离，循环 n 次可以确定所有点的最短距离

算法的正确性：

• 只需要证明每次迭代加入 S 的点一定是该点到 $1$ 号点的最短距离即可
• 显然第一次加入的点满足
• 假设第 $k$ 次加入的点 $v_k$ 满足 dist[k] 是 $1\to k$ 的最短距离
  • 反证法。假设第 $k+1$ 次加入的点不是最短距离
  • 也就是说存在另一条更短的路径 $u$，不妨设 $v_t$ 是该路径上不在 S 中的第一个节点
  • 由于 $\text{dist}[v_t]<\text{dist}[v_u]<\text{dist}[v_{k+1}]$
  • 这与 Dijkstra 算法每次从不在 S 中的选择距离 $1$ 号点最近的点这一说法相 矛盾
  • 也即 $\text{dist}[v_{k+1}]\le \text{dist}[v_t]$ 产生矛盾

AC849. Dijktra 求最短路 I

核心代码：

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i ++) {
        int t = -1;
        for (int j = 1; j <= n; j ++) {
            if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        st[t] = true;

        for (int j = 1; j <= n; j ++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }

    if (dist[n] == 0x3f3f3f3f) {
        return -1;
    }

    return dist[n];
}

• t = -1 其中 t 是不在 S 中的距离 $1$ 号点最近的点
  • 如果 t == -1 说明尚未开始比较，此时随便哪个来当 t 都可以
  • 有了 min 中的第一个元素之后才可以用 dist[j] < dist[t] 找出合适的 t = j
• 这里面用了邻接矩阵，因此是 for 循环了所有点来更新 dist 距离
• 如果 dist[n] 是初始化值，说明无法达到

堆优化 Dijkstra 算法

Dijkstra 算法最慢的一步在于找到 不在 S 中的距离 $1$ 号点最近的点。这个操作可以用小顶堆来进行优化，找最小的时间复杂度变为 $O(1)$。

• 手写堆：时刻保证堆中只有 $n$ 个数（支持修改元素写法）
• 优先队列：C++ 中的 priority_queue，Python 中的 set，使用冗余，堆中元素可能会有 $m$ 个

然而 $m\log n\sim m\log m$，因此我们都可以说堆优化版的 Dijkstra 算法时间复杂度都是 $m\log n$。

稀疏图的边的存储方式改为邻接表。

核心代码：

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.second;
        int distance = t.first;
        
        if (st[ver]) {
            continue;
        }
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) {
        return -1;
    }
    return dist[n];
}

• 默认的优先级队列是大顶堆，小顶堆为 priority_queue<PII, vector<PII>, greater<PII>> heap;
• 如果堆中元素是 pair，那么将会按照双关键字进行排序
• ver 是它的编号，如果 st[ver] 了，说明这个不过是一个冗余备份，跳过这次循环
• 否则，按照邻接表遍历它的所有直系节点（注意邻接表存储的是 直接相连的点）
  • 一旦出现了某个 dist[j] 发生修改，那么它就可能是隐藏的最小值，还是将其直接加入队列
  • 那么 dist[j] 可能会多次入队，不过无所谓，我们只取 top()

Bellman-Ford 算法

算法流程：

• 迭代 $n$ 次，每次循环所有边 a-(w)->b
• 更新方式：dist[b] = min(dist[b], dist[a] + w)（松弛操作）
• BF 算法可以证明循环完成后一定有 dist[b] <= dist[a] + w 对所有边都成立（三角不等式）
• BF 算法的存边方式可以用结构体来存 struct {} edge[M];

在我们求最短路的时候不能有 负权回路，此时最短路不存在。

Bellman-Ford 在迭代 $n$ 次后一定不能再继续松弛任意一条边，如果可以，则说明图中存在负权回路。如果当前迭代了 $k$ 次，那么 dist[b] 的含义就是从 $1$ 号点开始经过不超过 $k$ 条边走到 $b$ 点的最短路的距离。

算法证明：

我们需要证明，经过 $n$ 轮迭代，所有 最多经过 $n$ 条边的最短路径 已经被搜索到。

• 当 $n=1$ 时，结论显然成立，因为经过 1 条边只能是和 $1$ 号点相连的边，此时它们已松弛完毕
• 假设经过 $n=k$ 轮，所有最多经过 $k$ 条边的最短路径已经被搜索到
• 对于任意一条经过 $k+1$ 条边的最短路径，不妨设为 $1\to \cdots \to v_k\to v_{k+1}$。
  • 显然 $1\to \cdots \to v_k$ 最短路在上一轮已经搜索得到
  • 因此在经过 这一轮的松弛操作 后，可以保证 dist[k + 1] 也变成最短路
  • 因此所有经过 $k+1$ 条边的最短路径在第 $k+1$ 轮得到
• 最后一个问题，对于 $n$ 个点的无负权回路图，最短路可能经过 $\ge n$ 条边吗？
  • 不能，根据抽屉原理，此时至少会经过一个点两次，这就构成了环
  • 如果该环不是负环，那么完全可以在路径图中舍去这个环，得到的效果不变，同时路径长度减少，矛盾
  • 因此，最短路最多经过 $n-1$ 条边，也就是最多 $n-1$ 轮迭代后就有结果
  • 如果存在负权回路，那么第 $n$ 次迭代依然会进行松弛操作

其实所谓的 松弛操作 就是把这一条边绷紧。

Bellman-Ford 算法还有一个推论：最短路的 任何一段中间部分 都是最短路。

Bellman-Ford 算法的时间复杂度为 $O(n^2)$。

其实，如果有负权回路，最短路还是有可能存在的，只是说不一定存在。SPFA 算法要求图中不含负环，虽然 SPFA 各方面都优于 Bellman-Ford 算法。但是下面这道题不能用 SPFA 算法。

AC853. 有边数限制的最短路

为了防止发生 串联，需要在迭代之前保存上一次的 dist，避免出现以下这种情况：

• 当我们要求 $1$ 条边限制下到 $3$ 的最短路时，显然结果应该是 3
• 但是当我们按顺序更新时，先更新了 $1\to 2$ 的距离
• 此时再更新 $1\to 3$ 的距离时会用到更新这一轮刚更新的 $1\to 2$ 的距离，得到结果 2
• 其实这个时候边数已经是 2 了，因此矛盾（当然串联这种事在没有边数限制的题目中不需要考虑）

核心代码：

int bellman_ford() {
    for (int i = 0; i < k; i ++) {
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j ++) {
            int a = edges[j].a;
            int b = edges[j].b;
            int w = edges[j].w;

            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    
    if (dist[n] > 0x3f3f3f3f / 2) {
        return -1;
    }
    return dist[n];
}

这里需要 dist[n] > 0x3f3f3f3f / 2 是防止出现下面情况：

$5$ 和 $n$ 都无法到达，但是可以 $n$ 号点可能被 $5$ 号点更新掉，因此不能写 dist[n] == 0x3f3f3f3f。

SPFA 算法

SPFA 算法是对 Bellman-Ford 算法做的优化。

由于只有上一轮 dist[a] 变小了，这一轮的 dist[b] 才会变小。因此 SPFA 采用 BFS 做优化。

算法流程：

• 构造一个队列，将起点 1 放入队列中
• 入队的是当前这一轮变小的 dist[a]，因此队列中的是变小过的 dist[a]
• 变小过的 dist[a] 可能会引起它们相邻的 dist[b] 也变小（不是绝对的，因为有很多邻接节点）
• 只要队列不空，每次取出队头元素 t
  • 遍历 t 的所有出边 t -> j，更新 dist[j]
  • 如果更新成功，将 j 加入队列（注意判断 j 不在队列中才加入）
  • 思想：更新过谁，才用谁去更新其他人，没更新过的一定不会参与更新

SPFA 算法的实现和 Dijktra 算法很像。因此大部分正权图也可以用 SPFA 算法。

核心算法：

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

现在 SPFA 已经无法通过 Dijkstra 算法 II 这道题了：850. Dijkstra求最短路 II - AcWing题库。

SPFA 算法求负环

• dist[x] 表示当前 1->x 的最短距离
• cnt[x] 表示当前最短路的边的个数
• 只需要每次更新 dist 的时候更新 cnt[j] = cnt[t] + 1; 即可
• 如果出现 cnt[x] >= n 说明最短路边数超过点的个数，由抽屉原理知出现负环

注意，可能负环是 1 无法到达的孤岛，因此在初始队列中应该加入所有的点。

Floyd 算法

算法流程：三重循环

for (int k = 1; k <= n; k ++) {
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

基于动态规划：

• d[k, i, j] 表示从点 $i$ 只经过 $1\cdots k$ 这些中间点到达点 $j$ 的最短路
• 它从点 $k-1$ 转移过来，而这又分为两部分：
  • 最短路经过点 $k$：d[k, i, j] = d[k - 1, i, k] + d[k - 1, k, j]
  • 最短路不经过点 $k$：d[k, i, j] = d[k - 1, i, j]
• 因此：$D_{i,j,k}=min(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})$

显然在迭代的时候，第三维都是直接从 $k-1$ 转移到 $k$ 的，为了解决空间，直接覆盖掉即可：

$$D_{i,j}=min(D_{i,j},D_{i,k}+D_{k,j})$$

一些总结

• 堆优化的 Dijkstra 和 SPFA 的区别在于：
  • 堆优化的 Dijkstra 算法：优先队列，$O(m\log n)$
  • SPFA 算法：循环队列/队列，$O(n)$，最坏复杂度 $O(mn)$