最短路入门：算法选择与非负边权下的 Dijkstra

适合谁、学完能做什么

适合已经学习图的基本表示、BFS和优先队列，准备进入CSP-S/NOIP图论基础的学生。学完后，你应该能够：

• 判断题目是在求单源、单点对还是多源最短路。
• 根据边权条件选择BFS、Dijkstra、0-1 BFS、Bellman-Ford或Floyd。
• 用邻接表表示带权图。
• 理解“松弛”操作。
• 手动执行Dijkstra的距离更新。
• 使用优先队列实现非负边权下的Dijkstra。
• 正确处理不可达点、重复入队和大整数距离。

前置知识与网站关联

必须掌握图的顶点、边、边权、路径、邻接表、数组和循环，并了解优先队列的基本操作。

对应地图节点：graphs.dijkstra（Dijkstra）、graphs.path（最短路）、containers.49cce2491b（堆与优先队列）。

配套专题：CSP-S/NOIP|图论|Dijikstra 最短路-6 次短路-7|。

问题引入

把城市看成点、道路看成边、道路长度看成边权。给定起点后，求起点到其他城市的最短距离。

A --2--> B --3--> D
 \       |
  5      1
   \     |
    > C--+

从A到D可以经过不同路线。每当知道到达 u 的距离，又有一条 u → v 的边时，就要检查经过 u 到 v 是否更短，这个动作叫“松弛”。

先选择算法

本篇只处理“边权非负、一个起点、求到其他点最短距离”的情况。

核心概念与图示

定义：

dist[v] = 当前已知的从起点到 v 的最短距离

初始化时，起点距离为0，其他点设为很大的 INF。

若当前到 u 的距离是 dist[u]，有边 u → v，边权为 w：

如果 dist[v] > dist[u] + w：
    dist[v] = dist[u] + w

这就是松弛。

每轮从未确定的点中选择当前 dist 最小的点 u，再扫描 u 的所有出边。因为所有边权非负，当前最小的距离不会被未来路径改得更小。

优先队列中可能同时存在同一顶点的多个距离。例如先入队10，后来又入队6。弹出10时发现它不是当前 dist[u]，就应跳过旧状态。

算法步骤与正确性

1. 读入顶点数、边数和起点。
2. 使用邻接表存储带权边。
3. 初始化距离数组，设置 dist[start]=0。
4. 将 (0,start) 放入小根堆。
5. 取出当前距离最小的状态 (d,u)。
6. 如果 d != dist[u]，说明是旧状态，跳过。
7. 枚举 u 的每条出边并尝试松弛。
8. 距离变小就更新并重新入堆。
9. 队列为空时结束。

正确性依据是：当一个点 u 以当前最小距离从堆中取出时，任何经过未确定点的替代路径都必须先到达某个边界点；由于边权非负，该边界点的距离不会小于 u 的当前距离，因此不可能在之后产生更短的 u 路径。于是 u 的距离已经确定。不断松弛所有出边，就能确定所有可达点的最短距离。

如果有负权边，已经取出的点可能通过后面的负边变得更短，上述贪心证明失效。

完整 C++ 示例

语言：C++17。输入第一行 n m s，接下来输入 m 条有向边 u v w。点编号为1到n，边权非负；不可达点输出 INF。

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

struct Edge {
    int to;
    long long weight;
};

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

    int n, m, start;
    cin >> n >> m >> start;

    vector<vector<Edge>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n + 1, INF);
    using State = pair<long long, int>;
    priority_queue<State, vector<State>, greater<State>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [currentDistance, u] = pq.top();
        pq.pop();

        // 同一个点可能多次入队，旧状态不再处理。
        if (currentDistance != dist[u]) continue;

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            long long candidate = currentDistance + edge.weight;
            if (candidate < dist[v]) {
                dist[v] = candidate;
                pq.push({dist[v], v});
            }
        }
    }

    for (int v = 1; v <= n; ++v) {
        if (dist[v] == INF) cout << "INF";
        else cout << dist[v];
        if (v < n) cout << ' ';
    }
    cout << '\n';
    return 0;
}

如果道路是无向的，读入后需要同时加入两条边：

graph[u].push_back({v, w});
graph[v].push_back({u, w});

只有在题目明确道路双向时，才添加反向边。

复杂度与适用范围

设图有 n 个点、m 条边：

• 邻接表空间复杂度：O(n+m)。
• 二叉堆Dijkstra时间复杂度：O((n+m)log n)。
• 适用条件：边权全部非负，通常适合稀疏图。

存在负权、需要处理负环、边权只有0/1、要求所有点对最短路或图为DAG时，应根据条件选择其他算法。

易错点

1. 有负边仍然使用Dijkstra：负边会破坏“当前最小值已经确定”的结论。
2. 一入队就标记最终确定：入队只是发现候选距离，必须弹出当前最小且非旧的状态后再处理。
3. 不跳过旧状态：同一点可能多次入队，必须判断 currentDistance != dist[u]。
4. 使用过小的整数类型：多条边权相加可能超出 int，距离和边权建议使用 long long。
5. 混淆有向边和无向边：未明确为双向道路时不能自动添加反向边。

配套练习

以下题目来自本地 CSP-S/NOIP|图论|Dijikstra 最短路-6 次短路-7| 专题，题名、链接和难度已核对。当前内容工作室没有这些题的已发布题解，均只提供原题入口。

基础

1. P3371：【模板】单源最短路径（弱化版）（普及）：第一次实现邻接表、距离数组和优先队列版Dijkstra。
2. P1339：[USACO09OCT] Heat Wave G（普及）：练习带权图单源最短路和不可达情况。

变式

1. P2984：[USACO10FEB] Chocolate Giving S（普及）：在路线场景中巩固带权边和距离更新。
2. P1629：邮递员送信（普及）：练习有向图中的往返距离建模。

综合

1. P1821：[USACO07FEB] Cow Party S（普及）：练习多次最短路、反向图和距离统计。

自查与小结

完成本篇后，应能回答：BFS、Dijkstra、Bellman-Ford和Floyd各适合什么条件？什么是松弛？为什么Dijkstra要求边权非负？为什么同一点可能多次进入优先队列？为什么必须跳过旧状态？

能够手算三轮距离更新，独立写出优先队列版Dijkstra，并完成两道基础题和一道变式题，就可以继续学习Floyd、Bellman-Ford、0-1 BFS和更复杂的最短路模型。