Dijkstra：每次确定最近的点

一句话算法

每次确定还没定下来的点中离起点最近的一个，再用它更新邻居；边权非负，绕到后面再回来不会更近。

问题模型

给定有 $n$ 个点、$m$ 条边的有向图，点编号为 $1\sim n$，边权 $w\geqslant 0$。给定源点 $s$，求从 $s$ 到每个点的最短距离。

允许零权边、重边和自环；不可达的点单独标记。无向图的每条边存成两个方向即可。

这里比较的是整条路径的边权之和，不是经过的边数，也不是最后一条边的长度。边权全为 $1$ 时可以用 BFS；边权各不相同时，先发现的路径未必最短。

代码使用邻接表存图，并用小根堆取出当前最小距离。

核心直觉：先发现，不等于已确定

设 dis[v] 为目前找到的从 $s$ 到 $v$ 的最短路径长度。它是一个暂定距离：对应一条已经找到的路线，后面可能找到更短的。

沿边 $u\to v$ 尝试更新：

这一步叫作松弛，意思是“经过 $u$ 去 $v$，会不会更省？”

例如，以 $1$ 为起点：

flowchart LR
    a((1)) -->|8| b((2))
    a -->|2| c((3))
    c -->|1| b
    b -->|2| d((4))
    c -->|7| d

从 $1$ 出发，先发现到 $2$ 的路线长 $8$，到 $3$ 的路线长 $2$。如果一发现 $2$ 就认定答案是 $8$，便会漏掉 $1\to3\to2$ 这条长 $3$ 的路线。

因此要区分两个动作：

• 发现路线：得到一个候选距离，还可以改小。
• 确定答案：已经能证明没有更短路线，以后不必再改。

现在最有希望确定的是 $3$：已知走到它只要 $2$，其他候选路线更长，后续又不能靠负权边把费用减回来。于是先确定 $3$，把到 $2$ 的距离更新成 $3$，再确定 $2$。

还有一个疑问：某条尚未发现的绕路，会不会比当前最小值还短？ 证明中会沿着那条绕路，找到第一个尚未确定的点，说明它一定早就提供了一个更小的候选值。

算法步骤

先看不依赖堆的版本。用集合 $S$ 表示已经确定答案的点。

1. 初始化 dis[s] = 0，其他距离为无穷大，$S$ 为空。
2. 在 $S$ 外选择 dis 最小的点 $u$。若没有这样的点，或最小距离仍为无穷大，结束。
3. 确定 $u$ 的距离，把它加入 $S$。
4. 枚举 $u$ 的所有出边，用 dis[u] + w 松弛终点。
5. 回到第 2 步。

上图的过程如下，表中距离是本轮松弛结束后的值：

确定顺序按距离排列，不按点编号排列。 距离相同时，任取一个都可以。

算法证明

不变量：已经确定的点，其 dis 就是真正的最短距离。 每个有限的 dis 都来自实际路线，所以不可能小于真正的最短距离。

源点首先被选中。所有边权非负，从 $s$ 到自身的最短距离就是 $0$，不变量成立。

假设前面确定的点都正确，现在选中 $u$。记真正的最短距离为 $\delta(u)$。

在一条从 $s$ 到 $u$ 的最短路径上，找到第一个尚未确定的点 $y$，它的前一个点记为 $x$：

后半段中可以再次经过已确定的点；我们只用到 $y$ 是第一个尚未确定的点。

1. $x$ 已确定并松弛过 $x\to y$。到 $x$ 的最短距离不会超过这条路径的前缀长度，因此 dis[y] 不会超过这条路径到 $y$ 的前缀长度。
2. 剩余边权非负，所以该前缀长度不超过整条路径长度 $\delta(u)$。
3. $u$ 是尚未确定的点中 dis 最小的，所以 $dis[u]\leqslant dis[y]$。

记到 $y$ 的这段前缀长度为 $L$。候选路线不会优于真正的最短路，合在一起：

两端相同，所有不等号只能取等号，得到 $dis[u]=\delta(u)$。因此每一步都能安全确定一个点。

若仍有可达点尚未确定，在它的一条路径上取第一个尚未确定的点，同样会发现它已经被前驱更新成有限距离。因此算法结束后，剩下的无穷大距离恰好对应不可达点。

为什么不能有负权边

考虑 $s\to a$ 权值为 $2$，$s\to b$ 权值为 $5$，$b\to a$ 权值为 $-4$。算法会先想确定 $a$，但绕过 $b$ 后，到 $a$ 的距离其实是 $1$。

负权边破坏了“剩余路程不会减少费用”这一步，即使图中没有负环也一样。零权边只会让不等式取等号，不影响证明。

本文堆版本允许距离改小后再次入堆，在某些负权图上也可能算出正确结果，但此时“每个点只扩展一次”和复杂度保证已经失效，遇到可达负环还可能不断更新。不能用偶然算对的例子放宽非负边权的条件。 负权图应另看 Bellman-Ford。

堆优化：保存候选距离，跳过旧记录

朴素版本每轮扫描全部点找最小值，需要 $O(n)$。小根堆可以直接取出最小候选。

堆中存 (距离, 点编号)，距离在前。每次成功松弛，就把新记录放入堆。C++ 的 priority_queue 不方便修改堆内已有记录，所以保留旧记录，出堆时再判断它是否过期。

前面的例子中，到 $2$ 的距离从 $8$ 降到 $3$ 后，堆里同时存在 (8, 2) 和 (3, 2)。先弹出 (3, 2)，以后弹出 (8, 2) 时，发现它与 dis[2] = 3 不一致，直接跳过：

        
1
2
3
4

        ll du = q.top().first;   // 候选距离
int u = q.top().second;  // 候选距离对应的点
q.pop();
if (du != dis[u]) continue;
    

堆里始终保留着每个有限、尚未确定的距离的最新记录。跳过旧记录后，取出的有效记录就是算法要求的最小值。

本文只在距离严格变小时入堆，所以同一点不会产生两条相同距离的新记录；在非负权条件下，有效出堆后也不会再被改小。因此不必额外维护 vis。也可以使用“出堆时检查并设置 vis”的写法，但不能在入堆时就标记完成。

若只查询终点 $t$，可以在跳过过期记录之后、有效弹出 $t$ 时提前结束。第一次把 $t$ 放入堆时不能结束。 本文模板求所有点的距离，所以会跑到堆空。

复杂度分析

这里 $m$ 表示邻接表中存储的有向边条数；无向边拆成两条后只增加常数倍。

堆版本的计数依据是：初始化 $O(n)$；每个可达点有效扩展一次，所以每条边最多尝试一次松弛；每次成功松弛增加一条堆记录，总记录数至多 $m+1$，每次堆操作需要 $O(\log(m+2))$。

简单图有 $m=O(n^2)$，通常把堆版本写成 $O((n+m)\log n)$。允许大量重边时，保留 $\log m$ 的写法更准确。堆里可能同时存在同一点的多条记录，堆空间是 $O(m+1)$，不是 $O(n)$。

稀疏图通常选择堆版本。若 $m$ 接近 $n^2$，朴素版本的 $O(n^2)$ 可以省去堆操作；若使用邻接矩阵存图，其空间也会变为 $O(n^2)$。

代码模板

两个版本都按 $1\sim n$ 编号，都用 INF 表示不可达、用 dis 保存距离，接口一一对应：C++ 版是全局数组加普通函数，Python 版把状态收进函数内部。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

        #include <algorithm>
#include <functional>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<ll, int> State;  // (dis, u)：距离在前，小根堆才能先弹最小距离

const int maxn = 100000 + 5;         // 点数上限，按题面规模调整
const ll INF = (1LL << 62);          // 约 4.6e18：比任何合法最短距离都大

struct Edge {
    int to;  // 终点
    ll w;    // 边权，必须非负
};

vector<Edge> g[maxn];  // g[u]：从 u 出发的全部边
ll dis[maxn];          // dis[i]：s 到 i 的当前最短距离，INF 表示暂时不可达

// 点编号 1..n；换一张图前调用，避免多组数据残留旧边。
void init_graph(int n) {
    for (int u = 1; u <= n; ++u) g[u].clear();
}

// 加一条有向边 u -> v，权 w；无向边调用两次。
void add_edge(int u, int v, ll w) {
    g[u].push_back({v, w});
}

// 求 s 到 1..n 的单源最短路，结果写在全局 dis 里。
// 要求所有边权非负，且 n < maxn、合法的有限最短距离严格小于 INF。
void dijkstra(int n, int s) {
    fill(dis + 1, dis + n + 1, INF);  // 只清 1..n，dis[0] 不用

    // priority_queue 默认是大根堆，用 greater 反转成小根堆
    priority_queue<State, vector<State>, greater<State>> q;
    dis[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        ll du = q.top().first;  // 当前最小的候选距离
        int u = q.top().second;  // 候选距离对应的点
        q.pop();

        if (du != dis[u]) continue;  // 过期记录：u 已有更短距离，不再扫它的出边

        for (const Edge &e : g[u]) {
            // du < INF 且 w >= 0，仍先判结果再相加，避免大边权相加溢出
            if (e.w >= INF - du) continue;
            ll nd = du + e.w;
            if (nd >= dis[e.to]) continue;  // 只接受严格改善，零权环不会反复入堆
            dis[e.to] = nd;
            q.push({nd, e.to});
        }
    }
}
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

        # Dijkstra 非负权单源最短路（堆优化），点编号 1..n（dist[0] 不用）。
# dijkstra 返回 dist：INF 表示不可达；dist 是局部变量，换源点可以重复调用。
# 边权必须非负；出现负权边时本文的距离不再可信，应改用 Bellman-Ford 或 SPFA。
# Python 的 int 是任意精度，不必像 C++ 那样在相加前判溢出。

import heapq

INF = 1 << 62  # 哨兵，比任何合法最短距离都大

type WeightedAdj = list[list[tuple[int, int]]]  # graph[u]：若干 (终点 v, 边权 w)


def build_graph(
    n: int, edges: list[tuple[int, int, int]], directed: bool = True
) -> WeightedAdj:
    """把 (u, v, w) 边表转成 1..n 的邻接表；无向图把每条边存成两个方向。"""
    graph: WeightedAdj = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))
        if not directed:
            graph[v].append((u, w))
    return graph


def dijkstra(graph: WeightedAdj, source: int) -> list[int]:
    """返回 dist[1..n]；同一张图换源点可重复调用。"""
    n = len(graph) - 1
    dist = [INF] * (n + 1)
    dist[source] = 0
    heap: list[tuple[int, int]] = [(0, source)]  # (距离, 点编号)，距离在前才能按它比大小

    while heap:
        du, u = heapq.heappop(heap)
        if du != dist[u]:
            continue  # 过期记录：u 已有更短距离，不要再扫它的出边
        for v, w in graph[u]:
            nd = du + w
            if nd < dist[v]:  # 只接受严格改善，零权环上相等距离不再入堆
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    return dist
    

还原一条最短路径（进阶）

题目偶尔要求输出具体路线，而模板只求距离。这类题考试中很少出现，所以不放进代码模板，需要时按下面思路自己加几行。

要点只有一处：每次成功松弛时记下“$v$ 是从 $u$ 走过来的”，即 pre[v] = u。跑完后从终点顺着 pre 一直回走到源点，再把得到的序列翻转，就是一条从源点出发的最短路径。

在本文 C++ 模板基础上加一个全局数组和一段回走代码：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        int pre[maxn];  // pre[v]：最短路线上 v 的前一个点，源点与不可达点为 -1

// 在 dijkstra 的松弛成功分支里补一行
if (nd >= dis[e.to]) continue;
dis[e.to] = nd;
pre[e.to] = u;  // 只有严格改善时才改前驱，相等距离不动
q.push({nd, e.to});

// 跑完 dijkstra(n, s) 之后：还原源点 s 到 t 的一条最短路径
vector<int> path_to(int t) {
    if (dis[t] == INF) return {};  // 不可达，没有路径
    vector<int> path;
    for (int u = t; u != -1; u = pre[u]) path.push_back(u);
    reverse(path.begin(), path.end());  // 回走得到的是逆序，翻回来才是 s -> t
    return path;
}
    

别忘了在 dijkstra 开头把 pre 一起重置：fill(pre + 1, pre + n + 1, -1);，否则换源点会残留上一次的前驱。

几个容易踩的坑：

• pre 只在严格改善时更新。若写成 <=，零权边会让前驱互相指来指去，甚至成环，回走时死循环。
• 因此前驱总指向更早确定的点，path 一定走得回源点；源点的 pre 是 -1，正好当终止条件。
• 有多条等长最短路时，模板给出其中一条，不保证字典序最小，题目要求“字典序最小路线”时需要另加比较。
• path 里包含两端点，长度等于边数加一；不可达返回空数组，源点到自己只有源点一个点。
• 只需要终点 $t$ 时，可以在弹出 $t$ 的有效记录后立刻结束，但不能在 $t$ 刚入堆时就结束。

代码实现

下面是可单独编译运行的完整程序。

输入： 第一行 n m s，接下来 $m$ 行 u v w，表示有向边 $u\to v$。输入满足模板的非负边权与数值范围约定。

输出： 按点编号输出从 $s$ 出发的最短距离，不可达输出 -1。具体 OJ 的不可达标记可能不同，提交时按题面调整。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

        #include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<ll, int> State;  // (dis, u)：距离在前，小根堆才能先弹最小距离

const int maxn = 100000 + 5;  // 点数上限，按题面规模调整
const ll INF = (1LL << 62);   // 约 4.6e18：比任何合法最短距离都大

struct Edge {
    int to;  // 终点
    ll w;    // 边权，必须非负
};

vector<Edge> g[maxn];  // g[u]：从 u 出发的全部边
ll dis[maxn];          // dis[i]：s 到 i 的当前最短距离
int n;                 // 点数
int m;                 // 边数
int s;                 // 源点

// 加一条有向边 u -> v，权 w；无向边调用两次。
void add_edge(int u, int v, ll w) {
    g[u].push_back({v, w});
}

void read_input() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }
}

// 求 s 到 1..n 的单源最短路，结果写在全局 dis 里。
void dijkstra(int s) {
    fill(dis + 1, dis + n + 1, INF);

    // priority_queue 默认是大根堆，用 greater 反转成小根堆
    priority_queue<State, vector<State>, greater<State>> q;
    dis[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        ll du = q.top().first;   // 当前最小的候选距离
        int u = q.top().second;  // 候选距离对应的点
        q.pop();

        if (du != dis[u]) continue;  // 过期记录：u 已有更短距离，不再扫它的出边

        for (const Edge &e : g[u]) {
            // du < INF 且 w >= 0，仍先判结果再相加，避免大边权相加溢出
            if (e.w >= INF - du) continue;
            ll nd = du + e.w;
            if (nd >= dis[e.to]) continue;  // 只接受严格改善
            dis[e.to] = nd;
            q.push({nd, e.to});
        }
    }
}

void solve() {
    dijkstra(s);
    for (int v = 1; v <= n; v++) {
        if (v > 1) cout << ' ';
        // 不可达标记按题面调整，这里统一输出 -1
        if (dis[v] == INF) cout << -1;
        else cout << dis[v];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();
    return 0;
}
    

测试用例

普通情况：后来找到更短路线

输入对应前面的示意图：

4 5 1
1 2 8
1 3 2
3 2 1
2 4 2
3 4 7

输出：

0 3 2 5

到 $4$ 的最短路径是 $1\to3\to2\to4$，长度 $2+1+2=5$。堆中的 (8, 2)、(9, 4) 最后都会作为旧记录跳过。

边界情况：重边、零权环与不可达

5 6 1
1 2 9
1 2 4
2 3 0
3 2 0
3 3 0
4 5 1

输出：

0 4 4 -1 -1

重边自然取更优的距离；零权环与零权自环不会触发严格改善；$4$、$5$ 虽然有边相连，却都无法从源点到达。

距离超出 32 位整数

3 2 1
1 2 2000000000
2 3 2000000000

输出：

0 2000000000 4000000000

只有一个点且没有边时，输入 1 0 1，输出应为 0。

应用分类详解

Dijkstra 维护的是“从起点到各个状态的最小累计代价”。识别问题时，先确定状态是什么，再检查每次转移是否增加非负代价。

一、单源最小费用

识别信号： 一个起点，要求到多个位置的最短距离、最少时间或最低费用；费用可以累加，而且非负。

把位置当点，允许的移动当边，费用当边权。一次运行求出所有终点的答案，不需要对每个终点重新跑。若要求输出具体路线，按上一小节的办法再维护前驱。

二、所有点到同一个终点

识别信号： 多个出发点去同一个地点，或要求往返距离。

将每条 $u\to v$ 反向为 $v\to u$，权值不变。原图中从 $v$ 到 $t$ 的每条路径，都对应反图中从 $t$ 到 $v$ 的同长度路径。

所以在反图从 $t$ 跑一次，就得到所有点到 $t$ 的距离。求往返时，在原图和反图各跑一次，再按题意组合，不能把有向图的去程距离直接当作回程距离。

三、多个起点，求最近的一个

识别信号： 多个仓库、医院或出口，求每个点与其中最近一个设施之间的距离。

如果求的是“任一源点到 $v$”，把所有源点的距离设为 $0$ 并全部入堆，其余流程相同。等价做法是增加超级源点，向每个源点连一条零权边。本文模板按 $1\sim n$ 编号，超级源点可以用新编号 $n+1$。

若有向图问的是“从 $v$ 去最近的出口”，先反向建图，再把所有出口当源点。方向决定你算的是“从哪里来”还是“到哪里去”。

四、带使用次数的状态最短路

识别信号： 最多使用 $k$ 次免费机会、折扣或特殊操作；到达同一地点时，剩余机会不同会影响后续选择。

只记 dis[u] 不够。改用状态 $(u,j)$ 表示“到达 $u$，已经用了 $j$ 次机会”。对于一条费用为 $w$ 的边：

• 正常走：$(u,j)\to(v,j)$，代价 $w$。
• 免费走：若 $j<k$，则 $(u,j)\to(v,j+1)$，代价 $0$。

所有转移仍非负，便能在新状态图上运行 Dijkstra。若允许至多 $k$ 次，答案是 $\min_{0\leqslant j\leqslant k}dis[t][j]$，不能只看第 $k$ 层。复杂度按扩展后的点数、边数计算。

经典例题

1. P4779 【模板】单源最短路径（标准版）

luogu-P4779 题解

非负权有向图的直接应用。重点练习小根堆、严格松弛、跳过过期记录，以及使用足够宽的整数类型。先把这道题写熟，再考虑改变建图方式。

2. P1629 邮递员送信

luogu-P1629

每次从 $1$ 出发，送一件物品后返回。道路有方向，所以分别在原图和反图从 $1$ 跑最短路，答案为

这道题练习“多起点到同一终点”转换为反图单源最短路。题目保证任意两点互相可达。

3. P4568 [JLOI2011] 飞行路线

luogu-P4568 题解

把“用了几次免费机会”加入状态，按上一节的两类转移运行 Dijkstra。原图是无向图，两个方向都要考虑；题目按 $0\sim n-1$ 编号，使用本文模板时需要统一转换编号，或相应修改存储约定。

关键练习是分清“到达同一城市”与“到达同一状态”，并对终点的所有允许层数取最小值。