题解：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$ 次选择都成立，下面证明第 $k+1$ $k + 1$ 次选择是成立的：
- 不妨设第 $k+1$ 次选择的是 $v$ 。 $S$ 中的点都是确定最短路的，并且每个点进 $S$ 的时候，都松驰过出边。所以 $S$ 中的点不可能经过松弛更新 $dis_v$ 。
- 而 $V-S$ 中（ $V$ 是点集）其他的 $dis$ 值都比 $dis_v$ 大，所以边权都是非负的，所以 $V-S$ 中其他的点也都不可能经过松弛更新 $dis_v$ 了。
- $dis_v$ 已经收敛，必然满足 $dis_v = \delta(s, 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. 代码实现

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

CPP

#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;
}

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

文章操作