题解：P3371 【模板】单源最短路径（弱化版）

superLouis · 2025-03-18 23:11:52 · 题解

题解：P3371 【模板】单源最短路径（弱化版）

看到没有写时间复杂度 O(m \log n) 的 Dijkstra 原版（手写堆 + 索引数组），于是过来发一篇。其实这篇文章更像是算法理论的文章。

1. 算法实现

Dijkstra 算法由荷兰计算机科学家 E. W. Dijkstra 于 1956 年发现的一种最短路算法，是一种求解非负权图上单源最短路径的算法。

将结点分成两个集合：已确定最短路长度的点集（记为 S 集合）的和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。

初始化 dis_s=0，其他点的 dis 均为 +\infty。然后重复这些操作：

从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。
对那些刚刚被加入 S 集合的结点的所有出边执行松弛操作。

直到 T 集合为空，算法结束。

2. 正确性证明

令点 u 到点 v 的最短路长度是 \delta(u, v)。只需证明每次在 T 集合选择最短路长度最小的点 u 时，dis_u = \delta(s, u)。

我们可以采用数学归纳法：

第一次选择时，显然成立（选的点是起点 s）。
假设前 k 次选择都成立，下面证明第 k+1 次选择是成立的：
- 不妨设第 k+1 次选择的是 v。S 中的点都是确定最短路的，并且每个点进 S 的时候，都松驰过出边。所以 S 中的点不可能经过松弛更新 dis_v。
- 而 V-S 中（V 是点集）其他的 dis 值都比 dis_v 大，所以边权都是非负的，所以 V-S 中其他的点也都不可能经过松弛更新 dis_v 了。

得证。

3. 时间复杂度

我们先考虑朴素的实现方法。每次 2 操作执行完毕后，直接在 T 集合中暴力寻找最短路长度最小的结点。2 操作总时间复杂度为 O(m)，1 操作总时间复杂度为 O(n^2)，全过程的时间复杂度为 O(n^2 + m) = O(n^2)。

4. 优化

按照上面的做法，时间复杂度是 O(n^2)，适用于稠密图。但 n 到 10^5 量级时，基础的实现方法就超时了，所以考虑优化。

由于每次都是找到最小的距离，与二叉堆能实现的基本相似，考虑二叉堆的优化。

建立一个小根堆，把每个点的 dis 存在小根堆里，从而 O(\log n) 找到 dis 值最小的。
松弛出边时，同时也要更新小根堆里的 dis 值。

如果直接使用 priority_queue 容器，更新小根堆里的 dis 值操作就实现不了。但是可以采用不修改，直接将新的 dis 值加入堆的方法。这样虽然简洁省事，但是堆中最多有 m 个元素，导致时间复杂度 O(m \log m)。

但是为了让时间复杂度还是 O(m \log n)，我们必须手写堆，保证堆中最多不超过 n 个元素（当时研发出 Dijkstra 算法时还没有 priority_queue 呢）。为了更新小根堆里的 dis 值，我们可以建立一个索引数组（敲黑板），这样就可以在堆里面更新 dis 值啦。

5. 代码实现

我在代码里使用了前向星存储。

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 5e5 + 10;
constexpr int inf = 0x7fffffff;
int n, m, st, tot;
int heap[maxn], h[maxn], dis[maxn], idx[maxn];
struct node {
    int ptr, nxt, dis;
} e[maxn << 1];
inline void add(int u, int v, int w) {
    e[++tot] = node({h[u], v, w});
    h[u] = tot;
}
void up(int x) {
    for (int i = x, j = x >> 1; j; i = j, j >>= 1) {
        if (dis[heap[i]] < dis[heap[j]]) {
            swap(heap[i], heap[j]);
            swap(idx[heap[i]], idx[heap[j]]);
        } else break;
    }
    return;
}
void push(int x) {
    heap[++heap[0]] = x;
    idx[x] = heap[0];
    up(heap[0]);
}
void pop() {
    idx[heap[1]] = 0;
    idx[heap[heap[0]]] = 1;
    heap[1] = heap[heap[0]--];
    for (int i = 1, j = 2; j <= heap[0]; i = j, j <<= 1) {
        if (j < heap[0] && dis[heap[j + 1]] < dis[heap[j]]) j++;
        if (dis[heap[i]] > dis[heap[j]]) {
            swap(heap[i], heap[j]);
            swap(idx[heap[i]], idx[heap[j]]);
        } else break;
    }
    return;
}
void dijkstra() {
    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[st] = 0; push(st);
    while (heap[0]) {
        int u = heap[1]; pop();
        for (int v = h[u]; v; v = e[v].ptr)
            if (dis[e[v].nxt] > dis[u] + e[v].dis) {
                dis[e[v].nxt] = dis[u] + e[v].dis;
                if (!idx[e[v].nxt]) push(e[v].nxt);
                else up(idx[e[v].nxt]);
            }
    }
    return;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m >> st;
    for (int i = 1; i <= m; i++) {
        int u, v, w; 
        cin >> u >> v >> w;
        add(u, v, w);
    }
    dijkstra();
    for (int i = 1; i <= n; i++) cout << dis[i] << " \n"[i == n];
    return 0;
}