算法讲解064 必备 Dijkstra算法、分层图最短路

来源：算法讲解064【必备】Dijkstra算法、分层图最短路　·　2026-10-29

依据：视频字幕 2000 字

一句话概括

Dijkstra（迪杰斯特拉）算法在边权非负的图上，从单一源点求出到所有点的最短距离；「分层图最短路（layered graph shortest path）」是把「状态」乘进图里，用 Dijkstra 或 BFS 在扩展后的图上求最短路。

它解决什么问题

• 单源最短路（single-source shortest path）：给定源点 $s$，求 $s$ 到每个点 $v$ 的最短路径长度；不可达记为 $∞$。
• 有向图、无向图都行（无向边拆成两条有向边）。
• 边权必须非负。有负权边要用 Bellman-Ford / SPFA / Johnson。
• 分层图：当路径上除了「位置」还有「状态」（用了几个免费次数、当前方向、是否取过某物、钥匙集合……）时，把状态作为图的一维，变成普通最短路。

基础知识（前置概念，用大白话解释）

• 图（graph）：点集 $V$、边集 $E$。$n=|V|$，$m=|E|$。
• 边权（edge weight）：边上带的非负整数，路径长度 = 边权之和。
• 单源最短路：从一个源点出发到所有点的最短距离。
• 松弛（relax）：若已知 $dist[u]$，边 $(u,v,w)$ 满足 $dist[u]+w<dist[v]$，就更新 $dist[v]=dist[u]+w$。Dijkstra 的本质就是「按某种顺序反复松弛」。
• 优先队列 / 堆（priority queue / heap）：每次取出当前最小元素。C++ 的 std::priority_queue 默认是大根堆，要小根堆就存相反数或写比较器。
• 反向索引堆（indexed heap / decrease-key heap）：堆里存的是「点编号」，同时维护每个点在堆中的位置，支持 $O(log n)$ 的「修改某点的 key」和「删除」。Dijkstra 用它可以把「重复入堆」变成「原地改 key」，常数和堆大小都更小。竞赛里通常不手写，用「懒删除 + 普通堆」就够。
• 链式前向星（forward-star / adjacency array）：用数组 head[], to[], nxt[], w[] 存图，head[u] 是 $u$ 的第一条边，nxt 串起同起点的边。比 vector<vector<pair>> 更省内存、更快，$m$ 到 $2×10^6$ 级别时优势明显。
• 状态压缩（bitmask）：用一个整数的第 $i$ 位表示第 $i$ 个状态是否出现，$32$ 位整数可压 $32$ 个布尔状态。分层图里常把「已收集的钥匙集合」压成整数当一层。
• BFS（广度优先搜索）：边权全为 $1$（或全相等）时的最短路，$O(n+m)$。分层图若每层内边权为 $1$，可以直接 BFS 代替 Dijkstra。

原理（为什么这么做是对的，尽量给直觉）

核心直觉：把点分成两类——「已确定最短距离的」和「未确定的」。Dijkstra 每次从未确定集合中取出 $dist$ 最小的点 $u$，断言 $dist[u]$ 就是最终答案，然后拿 $u$ 去松弛它的出边。

为什么 $dist[u]$ 一定正确？ 反证：假设存在一条更短的路径到 $u$，它一定先从已确定集合出发、经过某个未确定点 $x$ 再进 $u$。由于边权非负，这条路径到 $x$ 的前缀长度 $≤$ 到 $u$ 的长度 $<dist[u]$，那 $x$ 的 $dist$ 就比 $u$ 还小，与「$u$ 是当前最小」矛盾。边权非负是这一步的关键：有负权时前缀可能比整条路径还长，反证失效。

为什么用堆？ 暴力版每轮扫一遍找最小是 $O(n^2)$。用堆维护「候选距离」，每次 $O(log n)$ 取出最小、$O(log n)$ 插入新候选，总 $O((n+m)log n)$。

懒删除（lazy deletion）：一个点可能被多次入堆（每次松弛成功都 push）。出堆时若 d != dist[u] 说明是旧记录，直接丢弃。这样不需要 decrease-key，代码短、常数可接受。堆大小上界 $O(m)$。

分层图为什么对？ 把「(位置, 状态)」当成新图的点，原图的一条边在新图里对应「状态转移后的一条边」。新图仍是普通图，边权仍非负，所以 Dijkstra 照样正确。状态维度通常很小（$≤ 10$ 或 $≤ 2^k$，$k≤ 10$），总点数 $n· 2^k$ 可控。

步骤（编号，可照着写）

普通 Dijkstra（堆优化 + 懒删除）

1. 建图（链式前向星或 vector 邻接表），边权非负。
2. dist[1..n] = INF，dist[s] = 0；小根堆放 (0, s)。
3. 循环直到堆空：

1. 弹出 (d, u)；若 d != dist[u] 跳过（懒删除）。

2. 遍历 $u$ 的出边 $(u,v,w)$：若 dist[u]+w < dist[v]，更新 dist[v] 并 push (dist[v], v)。

1. 结束后 dist[v] 即答案，INF 表示不可达。

分层图 Dijkstra

1. 确定状态维度：例如「最多 $k$ 次免费」，状态 = 已用免费次数 $0..k$。
2. 新点编号：id(u, c) = u*(k+1) + c（或 c*n + u，选一种统一）。
3. 对原边 $(u,v,w)$：

- 不免费：id(u,c) -> id(v,c)，权 $w$；

- 免费（若 $c<k$）：id(u,c) -> id(v,c+1)，权 $0$。

1. 在新图上从 id(s,0) 跑 Dijkstra，答案是 $min_c dist[id(t,c)]$。
2. 若所有边权为 $0/1$，改用 0-1 BFS（双端队列）或普通 BFS（全为 1 时）。

样例（一个具体小例子，带每步变化）

图：$A→ B$ 权 2，$B→ C$ 权 1，$C→ D$ 权 2，$B→ E$ 权 7，$C→ E$ 权 3，$A→ C$ 权 9。源点 $A$。

| 步骤 | 弹出 | dist[A] | dist[B] | dist[C] | dist[D] | dist[E] | 堆（d,u） |

|---|---|---|---|---|---|---|---|

| 初始 | — | 0 | ∞ | ∞ | ∞ | ∞ | (0,A) |

| 1 | (0,A) | 0 | 2 | 9 | ∞ | ∞ | (2,B),(9,C) |

| 2 | (2,B) | 0 | 2 | 3 | ∞ | 9 | (3,C),(9,C),(9,E) |

| 3 | (3,C) | 0 | 2 | 3 | 5 | 6 | (5,D),(6,E),(9,C),(9,E) |

| 4 | (5,D) | 0 | 2 | 3 | 5 | 6 | (6,E),(9,C),(9,E) |

| 5 | (6,E) | 0 | 2 | 3 | 5 | 6 | (9,C),(9,E) |

| 6 | (9,C) 旧记录，跳过 | 0 | 2 | 3 | 5 | 6 | (9,E) |

| 7 | (9,E) 旧记录，跳过 | 0 | 2 | 3 | 5 | 6 | 空 |

答案：$A→ B=2$，$A→ C=3$，$A→ D=5$，$A→ E=6$。注意 $A→ E$ 最优路径是 $A→ B→ C→ E$（$2+1+3=6$），不是 $A→ B→ E=9$。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（普通 Dijkstra，邻接表 + heapq）

import heapq

def dijkstra(n, adj, s):
    # adj[u] = [(v, w), ...]，点编号 0..n-1
    INF = float('inf')
    dist = [INF] * n
    dist[s] = 0
    pq = [(0, s)]                      # (距离, 点)
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:               # 懒删除：旧记录
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

C++（竞赛风，链式前向星 + 懒删除堆，1-indexed）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 200005;   // 点数上界
const int MAXM = 400005;   // 边数上界（无向图要 *2）
const ll INF = (ll)4e18;

int head[MAXN], nxt[MAXM], to[MAXM], wt[MAXM], ecnt;
void init(int n) {
    ecnt = 0;
    fill(head, head + n + 1, -1);
}
void addEdge(int u, int v, int w) {
    to[ecnt] = v; wt[ecnt] = w; nxt[ecnt] = head[u]; head[u] = ecnt++;
}

int n, m, s;
ll dist[MAXN];

void dijkstra(int src) {
    fill(dist, dist + n + 1, INF);
    dist[src] = 0;
    // 小根堆：存 (dist, u)，pair 默认按 first 升序
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;          // 懒删除
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e], w = wt[e];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s;
    init(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        addEdge(u, v, w);
        // 无向图再加 addEdge(v, u, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << -1 << ' ';
        else cout << dist[i] << ' ';
    }
    cout << '\n';
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

• 堆优化 Dijkstra：时间 $O((n+m)log m)$（懒删除堆大小上界 $O(m)$），空间 $O(n+m)$。最好/平均/最坏同阶，常数中等——priority_queue 的 push/pop 比手写堆慢一点，但 $m≤ 2×10^6$ 一般能过。
• 反向索引堆优化：时间 $O((n+m)log n)$，堆大小严格 $O(n)$，常数更小，但代码长、易错。竞赛里除非卡常，否则不写。
• 暴力 $O(n^2)$：稠密图（$m≈ n^2$，$n≤ 5000$）时反而比堆快，因为没 log。
• 分层图：点数 $n· S$、边数 $m· S$（$S$ 为状态数），时间 $O((nS+mS)log(mS))$，空间 $O(nS+mS)$。$S=2^k$ 时注意 $k≤ 10$ 左右，否则爆内存。
• BFS 版分层图：$O(nS+mS)$，无 log，最快。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 「从 $s$ 出发到每个点的最短距离」「边权非负」「$n,m≤ 2×10^5∼2×10^6$」→ 堆优化 Dijkstra。
• 「最多 $k$ 次免费 / 半价 / 翻转」「$k≤ 10$」→ 分层图 Dijkstra，状态 = 已用次数。
• 「钥匙 / 门」「收集若干物品」「状态是一个小集合」→ 状压分层图，状态 = bitmask。
• 「网格图 + 方向限制」「转向有代价」→ 状态 = 当前方向，分层图。
• 「边权只有 0 和 1」→ 0-1 BFS（双端队列），比 Dijkstra 快。
• 「边权全为 1」→ 普通 BFS。
• 反例：有负权边、要求负环检测 → 换 Bellman-Ford / SPFA；全源最短路 → Floyd（$n≤ 500$）或跑 $n$ 次 Dijkstra。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

模板 1：普通 Dijkstra（vector 邻接表，适合 $n,m≤ 2×10^5$）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<pair<int,int>>> adj(n + 1);   // (v, w)
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    vector<ll> dist(n + 1, INF);
    dist[s] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << (dist[i] == INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

模板 2：分层图 Dijkstra（最多 $k$ 次免费，$k≤ 10$）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k, s, t;
    cin >> n >> m >> k >> s >> t;
    // 点编号：id(u, c) = u * (k + 1) + c，u 从 0 开始，c 从 0 开始
    int S = k + 1;
    int N = n * S;
    vector<vector<pair<int,int>>> adj(N);
    auto id = [&](int u, int c) { return u * S + c; };
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        for (int c = 0; c <= k; c++) {
            adj[id(u,c)].push_back({id(v,c), w});           // 不免费
            if (c < k) adj[id(u,c)].push_back({id(v,c+1), 0}); // 免费一次
        }
    }
    vector<ll> dist(N, INF);
    int src = id(s, 0);
    dist[src] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    ll ans = INF;
    for (int c = 0; c <= k; c++) ans = min(ans, dist[id(t, c)]);
    cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}

边界与易错点（WA 的常见原因，越具体越好）

1. 边权有负数：Dijkstra 直接错，必须换算法。题目里出现「负权」「折扣可能为负」要警惕。
2. INF 不够大：int 的 0x3f3f3f3f 在 $n,m$ 大、边权大时可能溢出；用 ll 且 INF = 4e18，松弛时 d + w 不会溢出（$4×10^{18}+10^9$ 仍在 ll 范围）。
3. dist 用 int 存：路径长度可能超过 $2^{31}-1$（$2×10^5$ 条边、每条 $10^9$），必须 long long。
4. 懒删除判断写错：if (d != dist[u]) continue; 不能写成 if (d > dist[u])（虽然等价，但 d < dist[u] 不可能出现，写 != 最稳）。
5. 多测不清空：head[]、ecnt、dist[] 每轮都要重置；用 vector 时重新构造即可，用链式前向星要 fill(head, head+n+1, -1)。
6. 下标从 0 还是 1：模板统一 1-indexed 最省心；分层图 id(u,c) 的乘数别搞错（$u·(k+1)+c$，不是 $u· k+c$）。
7. 无向图忘加反向边：addEdge(u,v,w) 后要 addEdge(v,u,w)。
8. 分层图状态数爆炸：$k=20$ 时 $2^{20}× n$ 直接 MLE，先估内存：N * sizeof(ll) 别超 256MB。
9. 答案取错层：分层图终点答案要 $min_c dist[id(t,c)]$，不能只取 $c=0$ 或 $c=k$。
10. priority_queue 默认大根堆：忘了 greater<> 会取出最大值，结果全错。
11. 重边：Dijkstra 本身能处理重边（取最小即可），不用特判；但链式前向星建图时别去重，浪费。
12. 自环：边权非负时自环不会改进 dist，无害；但若写 d + w < dist[u] 且 $w=0$ 会死循环 push，懒删除能兜住，但常数变大。

同类题 / 变形（说清楚怎么改）

• 0-1 BFS：边权只有 0/1，把 priority_queue 换成 deque，$w=0$ 走 push_front，$w=1$ 走 push_back，$O(n+m)$。
• 多源最短路：所有源点 dist=0 一起入堆，跑一次 Dijkstra。
• **A\* 算法**：Dijkstra + 启发式估价 $h(u)$，priority_queue 按 dist[u]+h(u) 排序，用于「求 $s→ t$ 单条最短路」且 $h$ 可采纳时加速。
• 最短路计数：松弛成功时 cnt[v]=cnt[u]，相等时 cnt[v]+=cnt[u]（取模）。
• 次短路：每个点维护 dist1, dist2，松弛时同时更新，堆里存 (d, u, flag)。
• 分层图 + BFS：每层内边权为 1 时，直接 BFS 新图，$O(nS+mS)$。
• 状压分层图：状态是 bitmask，id(u, mask) = u * (1<<k) + mask，转移时 mask | (1<<i)。
• 方向分层：网格题「转向代价」，状态 = 当前朝向（4 种），id(u, dir)。

常见坑

• 用 map<int, vector<...>> 存图：常数巨大，$10^5$ 就 TLE，换 vector 或链式前向星。
• 用 list：缓存不友好，别用。
• #define int long long：全局改 int 会让 pair<int,int> 等变慢、printf 格式错，别用；该 ll 的地方显式写 ll。
• 多测时 priority_queue 没清空：每轮重新声明局部变量即可。
• 分层图里 k 次免费，状态是 $0..k$ 共 $k+1$ 种，不是 $k$ 种。
• 输出不可达：题目可能要求输出 -1 或 INF，看清题意。
• 链式前向星 MAXM 开小：无向图要 2*m，分层图要 (k+1)*m 量级，先算再开。

拓展（变体、实际用途、面试常问）

• 实际用途：地图导航（非负路权）、网络路由（OSPF 用 Dijkstra）、社交网络最短关系链、游戏寻路（网格 + A\*）。
• 面试常问：为什么不能有负权？——反证法里「前缀 $≤$ 全长」依赖非负；举反例：$A→ B=1$，$A→ C=2$，$C→ B=-2$，Dijkstra 先定 $B=1$，实际 $A→ C→ B=0$。
• 与 Prim 的关系：都是「每次取最小 + 松弛邻居」，区别是 Prim 维护「到已选集合的最小边」，Dijkstra 维护「到源点的最短距离」。
• Johnson 算法：有负权但无负环时，先跑 Bellman-Ford 重赋权使边权非负，再跑 $n$ 次 Dijkstra，$O(nmlog n)$。
• Dial 算法（桶优化）：边权是小整数时用桶代替堆，$O(m+C)$，$C$ 为最大边权。

自测 3 题（题目 + 折叠答案）

题 1：$n=4$，有向边 $1→2$ 权 1，$1→3$ 权 4，$2→3$ 权 2，$3→4$ 权 1，源点 1。求 dist[1..4]。