信竞学习笔记：Dijkstra

Tiger

发表于 2026-07-28

更新于 2026-07-28

学习笔记

2 1.1~1.4 分钟 504

注：这是本人的课堂笔记。

Dijkstra 算法是用来求解单源最短路径的一种算法。

Dijkstra 朴素算法

例题：P3371（可能会被卡 MLE）

在一个有边权（非负）有向图中，求单源最短路径。首先，初始化一个 $dist$ 数组为极大值（如 0x3f3f3f3f、INT_MAX，本题要求为 INT_MAX）、 $vis$ 数组为 false。假设要求 $1$ 号点到各点的最短路，我们称 $1$ 为源点。

在每次循环中，我们找到未被求出最短路的点中距离源点的距离最小的点，用它来更新其他点，这种操作叫作松弛。

核心代码如下：

memset(dis, 0x3f, sizeof dis);
dis[s] = 0;

for (int i=1; i<=n; i++) {
    int t = -1;
    for (int j=1; j<=n; j++) {
        if (!vis[j] && (t == -1 || dis[t] > dis[j])) {
            t = j;
        }
    }
    if (t == -1) break;
    vis[t] = 1;
    for (int j=1; j<=n; j++) {
        dis[j] = min(dis[j], dis[t] + g[t][j]);
    }
}

时间复杂度为 $O(n^2+m)$ 。

Dijkstra 堆优化算法

例题：P4779

注意到上述找点的过程可以用堆来进行优化。使用一个小根堆来维护 $dis$ 最小的节点：我们用一个结构体来保存点的编号和距离，并按 $dis$ 进行排序。刚开始放入源点，距离为 $0$ 。每次取出堆顶，验证其是否被访问过。若没被访问过，标记并进行松弛。每次松弛成功，就将松弛的边的终点和相应的 $dis$ 放入堆中，直至堆空。

数据结构定义如下：

struct edge {
    int v, w;
};
struct node {
    int dis, u;
    bool operator<(const node &other) const {
        return dis > other.dis; // 从堆底到堆顶递减
    }
};

const int N = 5e5 + 100;
int n, m, s, dis[N];
bool vis[N];
vector<edge> g[N];
priority_queue<node> pq;

核心代码如下：

memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
pq.push({0, s});

while (!pq.empty()) {
    int u = pq.top().u;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = 1;

    for (const auto &p : g[u]) {
        int v = p.v, w = p.w;
        if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            pq.push({dis[v], v});
        }
    }
}

时间复杂度为 $O(m \log m)$ 。