单点最短路算法 题解

知识点：图论 | Dijkstra | 贪心 | 优先队列（堆优化）

此文章的MarkDown、源码以及原图：点击跳转Gitee仓库

📗 题目描述

输入： 三个整数 $n, m, k$，分别表示 $n$ 个顶点、$m$ 条有向边，起点为 $k$。接下来 $m$ 行，每行三个整数 $u, v, w$，表示从 $u$ 到 $v$ 的有向边，边权为 $w$。

输出： $n$ 行，分别表示起点 $k$ 到各顶点的最短距离。若某点不可达，输出 INF。

无限大常量定义：

1
#define INF 0x3f3f3f3f

为什么用 0x3f3f3f3f 而非 0x7fffffff？

  • INF + INF = 0x7e7e7e7e < 0x7fffffff，不会溢出导致负数
  • 满足无穷大加法不溢出的要求，同时足够大（约 $10^9$）

📘 算法思想

Dijkstra 算法概述

Dijkstra 是一种贪心算法，用于在非负权图中求单源最短路。核心策略：

每次从尚未确定最短路径的节点中，选出距离起点最近的节点，将其标记为”已确定”，然后用它更新邻居的距离。

算法三步循环：

  1. 从堆中取出当前距离最小的未确定节点 $u$
  2. 将 $u$ 标记为已确定（加入集合 $S$）
  3. 用 $u$ 的出边松弛所有邻居 $v$：若 $\text{dist}[v] > \text{dist}[u] + w(u,v)$，则更新

算法手记

1

2

3

📙 数据结构

邻接表元素

1
2
3
struct Edge {
    int u, v, w;   // 有向边 u → v，边权为 w
};

小根堆元素

1
2
3
4
5
6
7
struct Node {
    int v, dist;   // 从起点到节点 v 的当前距离 dist

    bool operator<(const Node &n) const {
        return dist > n.dist;   // 重载为大于号，使 priority_queue 变为小根堆
    }
};

C++ 的 priority_queue 默认是大根堆。将 < 重载为 > 后，堆顶元素就是距离最小的。

容器总览

容器 类型 作用
cur vector<vector<Edge>> 邻接表存图
dist vector<int> 起点到各点的最短距离，初始 INF
inS vector<bool> 标记节点是否已确定最短路
pq priority_queue<Node> 小根堆，每次弹出距离最小的节点 
1
2
3
4
vector<vector<Edge>> cur(n);     // 邻接表
vector<int> dist(n, INF);        // 最短距离数组
vector<bool> inS(n, 0);          // 已确定标记
priority_queue<Node> pq;         // 小根堆

📕 算法流程详解

步骤 操作 说明
1 dist[k] = 0 起点距离设为 0
2 pq.push({k, 0}) 将起点入堆
3 pq.top() 取出最小节点 $u$ 每次选当前最近的未确定节点
4 if (inS[u]) continue 已确定则跳过（堆中可能有重复）
5 inS[u] = 1 标记为已确定
6 遍历 $u$ 的所有出边，尝试松弛 dist[v] = min(dist[v], dist[u] + w)
7 若松弛成功，pq.push({v, dist[v]}) 将更新后的邻居入堆
8 重复 3~7 直到堆空 所有可达节点均已确定

松弛操作核心：

1
2
3
4
if (dist[v] > dist[u] + w) {
    dist[v] = dist[u] + w;
    pq.push({v, dist[v]});
}

📓 完整代码

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
//
// Created by AKKO on 2026/4/22.
//
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

struct Edge {
    int u, v, w;   // 有向边 u → v，边权为 w
};

struct Node {
    int v, dist;   // 起点到 v 的当前距离

    bool operator<(const Node &n) const {
        return dist > n.dist;
    }
};

int main() {
    int n, m, k; cin >> n >> m >> k;  // n个点 m条边 k为起点

    vector<vector<Edge>> cur(n);      // 邻接表
    vector<int> dist(n, INF);         // 最短距离，初始INF
    vector<bool> inS(n, 0);           // 是否已确定
    priority_queue<Node> pq;          // 小根堆

    dist[k] = 0;                      // 起点距离为0

    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        cur[u].push_back({u, v, w});
    }

    pq.push({k, dist[k]});           // 起点入堆

    while (!pq.empty()) {
        Node node = pq.top();         // 取距离最小的节点
        pq.pop();
        int u = node.v;
        if (inS[u]) continue;         // 已确定则跳过
        inS[u] = 1;                   // 标记为已确定
        for (Edge e : cur[u]) {
            int v = e.v;
            int w = e.w;
            if (dist[v] > dist[u] + w) {  // 松弛
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});    // 更新后入堆
            }
        }
    }

    for (int i = 0; i < dist.size(); i++) {
        if (dist[i] == INF) cout << "dist[" << i << "]= INF" << endl;
        else cout << "dist[" << i << "]= " << dist[i] << endl;
    }
    return 0;
}

/*
input:
6 11 0
0 1 50
0 2 10
0 4 70
1 2 15
1 4 10
2 0 20
2 3 15
3 1 20
3 4 35
4 3 30
5 3 3

output:
dist[0]= 0
dist[1]= 45
dist[2]= 10
dist[3]= 25
dist[4]= 55
dist[5]= INF
*/

📝 算法要点总结

Dijkstra vs 其他最短路算法

算法 适用条件 时间复杂度 备注
Dijkstra（堆优化） 非负权图 $O((n+m) \log n)$ 本题使用
Dijkstra（朴素） 非负权图 $O(n^2)$ 稠密图可用
Bellman-Ford 允许负权边 $O(nm)$ 可检测负环
SPFA 允许负权边 均摊 $O(m)$ 最坏 $O(nm)$
Floyd 全源最短路 $O(n^3)$ 求任意两点间最短路

复杂度分析（堆优化）

指标 复杂度 说明
时间 $O((n+m) \log n)$ 每个节点最多入堆一次（实际可能多次），每次堆操作 $O(\log n)$
空间 $O(n+m)$ 邻接表 + 距离数组 + 堆

为什么 Dijkstra 不能处理负权边？

Dijkstra 的贪心策略要求：一旦节点 $u$ 被标记为”已确定”，dist[u] 就是最终最短路径。但若存在负权边，后续可能通过负权边找到更短的路径到 $u$，违反这一前提。

💡 易错提醒：

  • priority_queue 默认大根堆，operator< 要重载为 > 才能得到小根堆
  • 堆中可能存在同一节点的多条记录（不同距离），取出的已确定节点要 continue 跳过
  • 本题为有向图，只存单向边；若为无向图需存双向
  • 节点 5 无入边且不是起点，因此 dist[5] = INF（不可达）