1. 引言：最短路问题的魅力

想象一下，你身处一个错综复杂的城市交通网络，或者一个庞大的计算机网络，你想从一个起点出发，找到到达其他所有（或某个特定）地点耗时最短、成本最低或距离最近的路径。这就是最短路问题的核心。在算法竞赛中，最短路问题无处不在，它们可能直接出现，也可能隐藏在其他问题的子步骤中。掌握高效的最短路算法，是每一位竞赛选手的基本功。

Dijkstra 算法，正是解决 单源非负权最短路 问题最经典、最高效的算法之一。它的优雅在于其简洁的贪心思想，以及通过数据结构优化后达到的卓越性能。理解它，不仅能让你解决一大类问题，更能培养你分析问题、选择策略、优化实现的综合能力。

2. 初识 Dijkstra：核心思想与贪心本质

问题定义：单源最短路径

给定一个 带权有向图 ，其中是顶点集合，是边集合，每条边有一个权重。我们需要找到从指定的源点（source）到图中所有其他顶点的最短路径长度。

关键约束： Dijkstra 算法最核心的要求是，所有边的权重 必须是非负的，即对于所有。

我们将使用一个数组 dis 来存储从源点到各个顶点的当前已知最短路径长度。初始时，dis[s] = 0，而对于所有其他顶点，`dis[v] = \infty$（在代码中通常用一个足够大的数表示）。

贪心的直觉：每次选择“最近”的

Dijkstra 算法的灵魂在于它的 贪心策略。它维护一个已经确定了最短路径的顶点集合（我们称之为），初始时只包含源点。在每一步，算法会从那些尚未确定最短路径的顶点（即集合中的顶点）中，选择一个当前 dis 值最小的顶点，记为。

这个选择是贪心的：我们相信，当前距离源点 “看起来”最近的未确定顶点，它的这个 dis[u] 值就是它真正的最短路径长度。一旦选定了，我们就将它加入集合，并利用来尝试 松弛（Relaxation） 与它相邻的顶点。

松弛操作： 对于从出发的一条边，如果通过到达的路径比当前已知的到的路径更短，即，那么我们就更新。这表示我们找到了一个经过到达的更短路径。

可以想象成，源点是一个火源，火焰（最短路径的确信度）以最短距离为原则，一步步向外蔓延。每次总是选择离火源最近的那个未点燃的点，将其点燃（加入），然后让火焰从这个新点燃的点继续向其邻居蔓延（松弛）。

算法流程概览

初始化：
- 创建一个距离数组 dis，dis[s] = 0，dis[v] = \infty 对所有。
- 创建一个集合（或使用一个 vis 数组标记），初始为空（或 vis 全为 false）。
迭代次（或直到所有可达点都被处理）：
- 选择： 从中选择一个顶点，使得最小。
- 加入： 将加入（或标记 vis[u] = true）。
- 松弛： 对于从出发的每条边：
  - 如果，则更新。
结束： 算法结束后，dis[v] 就存储了从到的最短路径长度（如果不可达，则 dis[v] 仍为）。

3. Dijkstra 的正确性：为何贪心可行？

Dijkstra 算法的贪心选择如此直观，但为什么它是正确的？关键在于 非负边权 这个前提。

关键性质：非负边权

如果允许负权边，那么我们当前找到的“最短”路径，可能会因为后面经过一条负权边而变得更短，从而推翻之前的贪心选择。而非负边权保证了路径长度只会增加或不变，不会减少。

证明思路：反证法

证明 Dijkstra 算法正确性的经典方法是使用 反证法，结合 数学归纳法 的思想。我们要证明的核心是：当一个顶点被选入集合时，其当前的值就是从源点到的真正最短路径长度。

假设这个结论不成立。令是第一个被选入但其值不是到最短路径长度的顶点。
由于被第一个选入时，这必然是到的最短路径，所以。
既然不是最短路径，那么必然存在另一条从到的路径，其长度。

考虑这条更短的路径。这条路径必然会离开集合（因为）进入，然后再回到（正要被加入）。设是路径上第一个位于的顶点，其前一个顶点则位于中（可能是）。

示意图：，
路径 :

因为在被选择之前就已经加入，根据我们的假设（是第一个出错的顶点），已经是到的真正最短路径长度。
当被加入时，它必然松弛过它的邻居，包括。所以，当时必然有：

现在考虑路径从到的部分。由于边权非负，路径的长度必然小于等于整条路径的长度：

又因为且是到的最短路，所以：

因此，。

再考虑路径从到的部分。由于边权非负，这部分的长度。
所以，。

结合起来：

我们已知（这是我们的假设）。
所以，。

但是，在算法选择的那一刻，是中值最小的顶点。而此时也还在中（因为它是路径上第一个中的点，而是这条路径的终点，所以在之前或就是）。既然，那么算法应该选择而不是！这与我们假设算法选择了矛盾。

因此，最初的假设（存在一个被选入时不是最短路）不成立。

数学归纳：不变性维持

我们也可以用数学归纳法来理解。
归纳基础： 时，，是正确的。
归纳假设： 假设当时，所有的都是到的最短路径长度。
归纳步骤： 当算法选择第个顶点（是中值最小的）加入时，我们需要证明就是到的最短路径长度。这步的证明过程就如同上面的反证法。证明之后，新的集合仍然满足：所有的都是到的最短路径长度。

通过这种方式，我们可以确信 Dijkstra 算法在非负权图上找到的最短路径是正确的。

4. 朴素实现：邻接矩阵/邻接表 + 暴力查找

我们先来看一种最直观的实现方式，虽然效率不高，但有助于理解算法流程。

数据结构选择

图的表示：
- 邻接矩阵 (g[N][N])： 适用于 稠密图（边数接近）。g[u][v] 存储边的权重，若无边则存。空间复杂度。
- 邻接表 (vector<pair<int, int>> adj[N])： 适用于 稀疏图（边数远小于，竞赛中更常见）。adj[u] 存储一个列表，每个元素是 {v, w} 表示从到有一条权重为的边。空间复杂度。
距离数组： ll dis[N]。
标记数组： bool vis[N]，标记顶点是否已加入集合。

代码实现与分析

这里我们使用邻接表实现朴素 Dijkstra。

题意概括: 给定一个个点条边的带权有向图（边权非负），求源点到所有点的最短距离。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1005; // 示例最大点数
const ll INF = 1e18; // 定义无穷大

vector<pair<int, int>> adj[N]; // 邻接表存图 {邻接点, 边权}
ll dis[N]; // 存储源点到各点的最短距离
bool vis[N]; // 标记是否已确定最短路
int n, m, s; // 点数, 边数, 源点

void dijkstra() {
    for (int i = 1; i <= n; ++i) {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[s] = 0;

    for (int i = 0; i < n; ++i) { // 最多进行 n 次选择
        int u = -1;
        ll mind = INF;

        // 1. 选择: 在未访问点中找到 dis 最小的点
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && dis[j] < mind) {
                mind = dis[j];
                u = j;
            }
        }

        // 如果找不到可选的点 (剩余点不可达)，或者所有点都已访问，则退出
        if (u == -1) {
            break;
        }

        // 2. 加入: 标记 u 为已访问
        vis[u] = true;

        // 3. 松弛: 更新 u 的邻居的最短距离
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> s;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        // 如果是无向图，需要加反向边: adj[v].push_back({u, w});
    }

    dijkstra();

    for (int i = 1; i <= n; ++i) {
        if (dis[i] == INF) {
            cout << "INF "; // 或者按题目要求输出
        } else {
            cout << dis[i] << " ";
        }
    }
    cout << endl;

    return 0;
}

复杂度分析:

时间复杂度：
- 外层循环最多执行次。
- 内部的选择步骤（步骤 1）需要遍历所有个顶点来找到 dis 最小的未访问顶点，复杂度为。
- 内部的松弛步骤（步骤 3）对于一个顶点，需要遍历其所有出边。在整个算法过程中，每条边最多被松弛一次。总的松弛操作复杂度，如果用邻接表是，如果用邻接矩阵是。
- 主导复杂度来自选择步骤：总时间复杂度为。对于邻接矩阵实现，松弛也是（遍历一行），总复杂度为。通常我们记为 ****。
空间复杂度：
- 邻接表：。
- 邻接矩阵：。
- 辅助数组 dis 和 vis：。

复杂度瓶颈

的时间复杂度在较大（例如）时是无法接受的。其核心瓶颈在于每次都需要的时间来查找 dis 值最小的未访问顶点。如何加速这个查找过程？这自然引出了优先队列优化。

5. 效率飞跃：优先队列优化

为了解决朴素实现中查找最小 dis 值的瓶颈，我们可以使用一种更高效的数据结构来维护未访问顶点的距离信息——优先队列（Priority Queue），通常用 二叉堆（Binary Heap） 实现。

瓶颈突破：快速找到最小距离点

优先队列（最小堆）允许我们高效地执行以下操作：

插入（Insert）： 将一个带优先级的元素加入队列。复杂度，其中是队列大小。
查询最小（Find-Min）： 查看优先级最高的元素（即 dis 最小的顶点）。复杂度。
删除最小（Extract-Min）： 移除并返回优先级最高的元素。复杂度。
减小优先级（Decrease-Key）： 降低某个元素的优先级（即松弛操作后更新 dis 值）。标准库的 priority_queue 不直接支持对任意元素进行 Decrease-Key，但我们可以通过插入新值和“懒惰删除”策略来模拟。

优先队列（堆）的应用

我们将优先队列用于存储 pair<ll, int>，即 {当前距离, 顶点编号}。优先队列会根据距离（第一个元素）自动维护最小值在队首。

算法流程（优先队列优化版）：

初始化：
- dis 数组初始化同前（dis[s]=0, 其他为）。
- vis 数组初始化为 false（或者可以省略 vis，见后文）。
- 创建一个 最小优先队列 pq。
- 将源点信息 {0, s} 插入 pq。
循环直到队列为空：
- 提取最小： 从 pq 中提取距离最小的顶点信息 {d, u}（即 pq.top() 和 pq.pop()）。
- 有效性检查（关键）：
  - 如果已经被访问过（vis[u] == true），说明这个 {d, u} 是旧的、冗余的信息（因为我们可能因为松弛多次将一个顶点以不同距离加入队列），直接 continue 跳过。
  - 或者，如果提取出的距离大于当前记录的 dis[u]（这意味着在入队后，又通过其他路径找到了一个更短的路径到达，并更新了 dis[u]$），这个 {d, u} 也是过时的信息，continue跳过。**这个检查可以替代vis` 数组的作用，是实现“懒惰删除”的核心。** 通常推荐使用这个检查，因为它更简洁。
- 标记访问（如果使用 vis 数组）： 标记 vis[u] = true。
- 松弛： 对于从出发的每条边，权重为：
  - 如果：
    - 更新。
    - 将新的、更优的顶点信息 {dis[v], v} 插入 pq。
结束： 算法结束后，dis 数组即为所求。

代码实现与分析（竞赛推荐）

题意概括: 同上，给定一个个点条边的带权有向图（边权非负），求源点到所有点的最短距离。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 5; // 竞赛中常见点数范围
const ll INF = 1e18;

vector<pair<int, int>> adj[N]; // {邻接点, 边权}
ll dis[N]; // 最短距离
// bool vis[N]; // 可以省略 vis 数组
int n, m, s;

// 定义优先队列存储的元素类型和比较方式 (最小堆)
using P = pair<ll, int>; // {距离, 顶点编号}
priority_queue<P, vector<P>, greater<P>> pq;

void dijkstra() {
    for (int i = 1; i <= n; ++i) {
        dis[i] = INF;
        // vis[i] = false;
    }
    dis[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        // 1. 提取最小距离点
        auto [d, u] = pq.top(); // C++17 structured binding
        pq.pop();

        // 2. 有效性检查 (懒惰删除)
        // 如果这个状态是旧的 (找到了更短的路到u), 则跳过
        if (d > dis[u]) {
            continue;
        }
        // 如果使用 vis 数组:
        // if (vis[u]) continue;
        // vis[u] = true; // 放在这里标记

        // 3. 松弛 u 的邻居
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v}); // 加入新的更优状态
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> s;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        // 无向图加反向边: adj[v].push_back({u, w});
    }

    dijkstra();

    for (int i = 1; i <= n; ++i) {
        cout << dis[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

复杂度分析:

时间复杂度：
- 每个顶点最多被成功提取（即 d <= dis[u]）并用于松弛一次。
- 每次松弛一条边，如果更新了 dis[v]，会执行一次 pq.push() 操作，复杂度（优先队列的大小最多为，但在稀疏图中可能远大于，而堆的大小与图中节点有关，更精确地说是或，通常认为，所以和是同阶的，记为）。
- 每条边最多导致一次成功的松弛和一次入队操作。总共最多有次 push。
- 每次从优先队列提取最小元素 pq.pop() 的复杂度是。最坏情况下，每次松弛都入队，队列中可能有个元素（包含冗余状态）。因此，while 循环和 pop 操作的总次数可能达到。
- 综合起来，总时间复杂度是或。在和关系不定的情况下，有时也写成，因为至少有次成功的 pop 和次 push（如果图连通）。对于连通图，所以是一个很好的近似。这是竞赛中最常用的 Dijkstra 实现及其复杂度。
空间复杂度：
- 邻接表：。
- dis 数组：。
- 优先队列：最坏情况下可能存储个元素（包含冗余），所以是。
- 总空间复杂度主要是。

“懒惰删除”策略解析

注意到在优先队列实现中，当松弛操作发生时，我们并没有去修改优先队列中可能已经存在的、关于顶点的旧的（更大的）距离信息。我们只是简单地将新的、更优的 {dis[v], v} 插入队列。

这样做是因为 std::priority_queue 不支持直接修改队列内部元素的优先级。那么旧的信息怎么办？

这就是“懒惰删除”的核心：我们不主动删除旧信息，而是在从队列顶端取出元素 {d, u} 时进行检查。
检查 if (d > dis[u]) 的含义是：当前取出的这个状态 {d, u}，其距离是否比我们目前记录的到的最短距离 dis[u] 还要大？
如果，说明在我们把 {d, u} 加入队列之后，又通过其他的路径找到了一个到达的更短方式，并且已经更新了 dis[u]$ 并将那个更优的状态也加入了队列。因此，当前取出的这个 {d, u} 是一个 **过时的、无效的状态**，我们直接忽略它（continue`），相当于把它“懒惰地删除”了。

只有当时（由于我们只在 dis 减小时才入队，且是从 dis 值来的，所以实际只会是），才说明这是当前到达的已知最短路径对应的状态，我们才处理它（进行松弛操作）。

这种策略避免了复杂的堆修改操作，代码简洁，效率也足够高，是竞赛中的标准实践。它也解释了为什么优先队列的大小最坏可能是而不是。

6. 实战细节与常见陷阱

魔鬼在细节中。即使理解了算法原理和核心代码，实战中也可能因为一些细节问题翻车。

初始化：无穷大与源点距离

无穷大的选择： INF 必须足够大，要大于任何可能的最短路径长度。如果路径长度可能很大（例如），需要确保 INF 不会溢出 long long（如果使用了 long long），并且 INF + w 也不会轻易溢出。通常 1e18 对于 long long 是安全的。
源点距离： 必须将 dis[s] 初始化为 0，其他所有点初始化为 INF。这是算法的起点。
优先队列： 初始时只将 {0, s} 放入优先队列。

整数溢出：`long long` 的必要性

竞赛题目中，边权和顶点数可能很大，导致最短路径长度超过 32 位整数（int）的范围（约）。例如，一条包含条边，每条边权为的路径，总长度可达。

务必使用 long long (即 ll) 存储距离 dis 数组和优先队列中的距离 d。 否则，即使是很简单的 Dijkstra 题目也可能因为溢出而得到错误答案。

检查 dis[u] + w < dis[v] 时，也要注意 dis[u] + w 本身是否可能溢出。如果 dis[u] 已经是 INF，则 dis[u] + w 可能会溢出。通常，如果 dis[u] 是 INF，这个判断 dis[u] + w < dis[v] 不会成立（除非 dis[v] 也是 INF，但即使更新了也没意义），所以一般还好。但如果 dis[u] 不是 INF 但已经很大，dis[u] + w 仍需小心。不过在非负权图中，这个问题相对少见，因为最短路通常不会比 INF 大。

重边与自环

重边（Multiple Edges）： 即两个顶点之间有多条边。Dijkstra 算法（无论是朴素还是优先队列版本）自然地处理了重边。松弛操作 dis[u] + w < dis[v] 会自动选择权重最小的那条边来更新 dis[v]。所以在建图时，即使有多条边，直接加入邻接表即可。
自环（Self-loops）： 即形如的边。如果自环权重，它不会影响最短路径结果，因为通过自环不会让路径变短。松弛 dis[u] + w(u, u) < dis[u] 永远不会成立。如果自环权重，它也没有影响。如果允许负权自环，Dijkstra 本身就不适用。因此，通常可以忽略自环或者照常加入图中。

无法到达的节点

如果从源点无法到达某个顶点，那么 dis[v] 将保持其初始值 INF。在输出结果时，需要判断 dis[v] 是否等于 INF，并按题目要求输出（可能是 “INF”, -1, 或一个特定的大数）。

路径重构：记录前驱节点

Dijkstra 算法计算了最短路径的长度，但有时题目还需要输出具体的路径。为此，我们需要在松弛操作时记录下每个顶点的前驱（predecessor）。

增加一个 pre 数组：int pre[N]。
初始化：可以将 pre 都初始化为 0 或 -1。

修改松弛操作：

if (dis[u] + w < dis[v]) {
    dis[v] = dis[u] + w;
    pre[v] = u; // 记录 v 的前驱是 u
    pq.push({dis[v], v});
}

重构路径： 要找到到的最短路径，可以从开始，不断通过 pre 数组回溯，直到到达。

vector<int> getPath(int t) {
    vector<int> path;
    if (dis[t] == INF) return path; // 不可达
    for (int cur = t; cur != 0; cur = pre[cur]) { // 假设 pre[s] = 0
        path.push_back(cur);
        if (cur == s) break; // 防止源点未设置pre导致死循环
    }
    reverse(path.begin(), path.end()); // 回溯得到的是反向路径，需要翻转
    return path;
}

注意 pre[s] 的处理，可以约定 pre[s] = 0 或 s 本身，并在回溯时正确终止。

7. Dijkstra 的局限：负权边的挑战

我们反复强调 Dijkstra 的前提是 非负边权。如果图中存在负权边，Dijkstra 的贪心策略就可能失效。

反例：贪心失效

考虑下图：
(权重 3)
(权重 5)
(权重 -4)

dis[s]=0, dis[A]=INF, dis[B]=INF. 优先队列 { (0, s) }。
取出 s。松弛 : dis[A]=3, pq.push({3, A})。松弛 : dis[B]=5, pq.push({5, B})。队列 { (3, A), (5, B) }。
取出 A (因为 3 < 5)。dis[A]=3 被确认为最短路。松弛 : dis[A] + w(A, B) = 3 + (-4) = -1。因为，更新 dis[B]=-1，pq.push({-1, B})。队列 { (-1, B), (5, B) }。
取出 { -1, B }。dis[B]=-1 被确认为最短路。
取出 { 5, B }。发现 5 > dis[B]=-1，忽略。
队列为空，结束。

最终结果 dis[A]=3, dis[B]=-1。

问题： 当被选出时，我们“过早地”认为到的最短路就是 3。但实际上，存在一条更长的路径（如果存在的边），或者像这个例子中，存在一条通过到达的路径，其长度，比直接的路径（长度 5）要短。Dijkstra 算法在确定的最短路时，没有预见到未来可能通过负权边获得“收益”。

核心原因： 负权边破坏了“一旦一个节点被确定最短路，其距离就不会再变小”的性质。

替代方案：Bellman-Ford 与 SPFA

当图中存在负权边时，需要使用其他算法：

Bellman-Ford 算法： 可以处理带负权边的单源最短路问题，并且可以检测 负权环（Negative Cycle）。时间复杂度。如果图中没有负权环，它能正确计算最短路；如果存在负权环，它能报告出来。
SPFA (Shortest Path Faster Algorithm)： 是 Bellman-Ford 的队列优化版本。在随机数据和稀疏图上通常表现比 Bellman-Ford 好，期望复杂度（是个小常数），但最坏情况下仍然是，并且可能被特殊构造的数据卡到这个最坏情况。SPFA 也能检测负权环。

选择：

如果保证 边权非负，优先使用 Dijkstra（优先队列版），因为通常远优于。
如果 可能存在负权边，但 保证没有负权环，可以使用 Bellman-Ford 或 SPFA。SPFA 在很多情况下更快，但在可能被卡时 Bellman-Ford 更稳定。
如果 可能存在负权环，必须使用 Bellman-Ford 或 SPFA 来检测，并按需处理（通常是报告存在负环，因为负环意味着最短路可能无限小）。

8. Dijkstra 的延伸与应用

Dijkstra 算法的思想和框架可以应用到更广泛的问题中。

网格图上的 Dijkstra

很多问题发生在二维网格上，例如迷宫寻路。可以将网格抽象成图：

顶点： 每个格子是一个顶点。
边：如果可以从格子移动到相邻格子（例如上下左右移动），则在顶点和之间连边。
权重： 边的权重通常是 1（表示移动一步），或者是移动到目标格子的代价（例如，地形的耗时）。

然后就可以在转换后的图上跑 Dijkstra。顶点可以用 pair<int, int> 表示，或者将其映射到一个整数编号 id = r * num_cols + c。

注意： 如果所有边的权重都是 1（或 0），那么使用 广度优先搜索 (BFS) 会更高效，时间复杂度为（在网格中即）。如果边权只有 0 和 1，可以使用 0-1 BFS（使用双端队列 deque 实现），复杂度也是。只有当边权有多种非负值时，才需要 Dijkstra。

状态压缩 + Dijkstra

有时，图的“顶点”不仅仅是物理位置，还包含了一些状态信息。例如：

带有钥匙的迷宫： 状态可能是 (当前位置, 持有的钥匙集合)。
限制步数/油量的移动： 状态可能是 (当前位置, 剩余步数/油量)。

我们可以将每个 (位置, 状态) 组合视为一个 超级节点。图的边表示从一个状态到另一个状态的转移，边的权重是这次转移的代价。

例子：收集钥匙
假设迷宫中有种钥匙，分布在不同位置。要从起点到终点，必须收集到所有种钥匙。

状态： (u, mask)，其中是当前所在格子，mask 是一个位的二进制数，表示当前持有的钥匙集合（第位为 1 表示持有第种钥匙）。
顶点： 共有个状态顶点（是格子数）。
边：
- 从 (u, mask) 移动到相邻格子 (v, mask)，如果移动合法，则有一条边，权重为移动代价（通常是 1）。
- 如果格子处有第种钥匙，并且 mask 的第位是 0，则可以从 (u, mask) 转移到 (u, mask | (1 << j))，这条边的权重是 0（拾取钥匙不耗时）。
- 如果格子是一个需要第种钥匙才能打开的门，并且 mask 的第位是 1，则可以从 (u, mask) 移动到门后的格子 (v, mask)，权重为移动代价。

在这个 状态空间图 上运行 Dijkstra，起点是 (起始位置, 初始钥匙状态)，终点是所有 (终点位置 T, 最终钥匙状态 mask) 中距离最短的那个（mask 必须包含所有需要的钥匙）。

复杂度： 状态数乘以边的对数，即，其中是状态图中的边数。这种方法适用于较小的情况（通常左右）。

第 K 短路问题（简介）

寻找从到的第短路径（允许重复经过点和边）。这不是一个简单的 Dijkstra 应用，通常需要更复杂的算法，如 A* 算法结合 Dijkstra，或者维护每个节点的前个最短距离。这超出了基础 Dijkstra 的范畴，但了解其存在有助于拓宽视野。

对偶图与最短路（进阶）

在平面图（可以画在平面上且边不交叉的图）中，最短路问题有时可以转化为其 对偶图（Dual Graph）上的最小割问题，或者反之。这涉及到更深的图论知识，如最大流最小割定理，通常在较高难度的题目中出现。

9. 解题思维：如何识别 Dijkstra 模型

面对一个算法题，如何判断它是否可以用 Dijkstra 解决？

核心特征：单源、非负权、最短路

最直接的线索：

单源（Single Source）： 问题要求从一个明确的起点出发，计算到其他点（或特定终点）的某种累计量的最小值。
非负权（Non-negative Weights）： 状态转移的代价（边的权重）必须是非负的。这是使用 Dijkstra 的硬性前提。如果出现负权，立刻考虑 Bellman-Ford/SPFA。
最短路（Shortest Path）： 问题的目标是找到一个最小值，这个值通常是路径上各段代价的累加。

隐式图：状态转移的抽象

很多题目不会直接给你一个图。你需要自己 构建图模型。

识别节点： 问题的“状态”是什么？它们能否作为图的节点？（例如：位置、(位置, 状态)、数字、字符串等）
识别边： 状态之间如何转移？一次合法的操作是什么？这对应图的边。
识别权重： 每次转移的代价是多少？这对应边的权重。

如果构建出的图满足单源、非负权、求最短（最小代价）这三个条件，那么 Dijkstra 就是一个有力的候选算法。

模型转换：将问题转化为图论模型

例子：

最少操作次数： 如果每次操作代价为 1，这就是一个边权为 1 的最短路问题（可以用 BFS 或 Dijkstra）。
最小花费/时间： 直接对应边权。
数字变换： 数字可以通过某种操作变成数字，代价为。求到的最小总代价。节点是数字，边是操作，权重是代价。
同余最短路： 问题涉及模意义下的可达性和最小代价，例如用给定面额的硬币凑出某个金额（或模的余数），要求使用硬币数量最少。可以构建一个以余数为节点，边表示加一个硬币面额的图。

关键在于抽象和建模的能力。看到问题，要思考它内在的联系和转移关系，能否映射到一个图上。

10. 写在最后

Dijkstra 算法简洁、高效，应用广泛。通过本文，我们一起：

理解了 Dijkstra 的 核心贪心思想 及其基于 非负权 的 正确性证明。
掌握了 朴素实现（）和 优先队列优化（）的代码，特别是竞赛中常用的后者。
熟悉了 “懒惰删除” 等实现细节。
探讨了 整数溢出、路径重构、负权边处理 等实战要点和陷阱。
了解了 Dijkstra 在 网格图、状态压缩 等场景下的延伸应用。
培养了 识别 Dijkstra 模型 的解题思维。

精通 Dijkstra 算法，不仅仅是记住代码模板。更重要的是理解其原理，知道它的能力边界（非负权），能够在各种问题背景下灵活地构建图模型并套用它，甚至在需要时进行适当的修改和扩展。

Dijkstra