深入理解单源最短路径算法：Dijkstra与SPFA的全面对比

核心逻辑与数学原理

单源最短路径（Single Source Shortest Path, SSSP）问题的本质是在权值图 $G=(V, E)$ 中，寻找从特定源点 $s$ 到其余所有节点 $v \in V$ 的最小边权值和路径。在 NOIP 体系下，Dijkstra 堆优化算法与 SPFA 算法代表了两种截然不同的拓扑逼近范式。

1. 贪心范式：Dijkstra 算法

Dijkstra 算法的核心是基于拓扑蓝白点集合的贪心扩张。

数学原理：将节点分为两个集合：已确定最短路径的熟化点集 $S$（蓝点），和未确定的悬空点集 $T$（白点）。每次从 $T$ 中强制挑选一个当前距离源点 $s$ 最近的节点 $u$，将其并入 $S$。
无负权依赖：该算法成立的数学基石是单调非降性。若图中存在负权边，已并入 $S$ 的节点的最短路径可能被后续的负权回路或负边刷新，导致贪心策略崩溃。
复杂度定理：配合优先队列（二叉堆）维护 $T$ 集合的最小值，单次松弛复杂度为 $O(\log V)$，总时间复杂度严格控制在 $O((V+E)\log V)$。

2. 动态逼近范式：SPFA 算法

SPFA（Shortest Path Faster Algorithm）本质上是带队列优化的 Bellman-Ford 算法，属于动态规划的迭代逼近。

数学原理：对图进行多轮松弛。只有在上一步中被成功更新了最短路径估计值的节点，其出边才有可能触发后续节点的松弛。因此，用一个队列存储“由于自身值变小，从而有能力去松弛其他节点”的节点。
生死边界（算法退化）：SPFA 的理论平均复杂度为 $O(kE)$（$k$ 为常数，一般 $k \le 2$）。然而，其最坏时间复杂度为标准的 $O(VE)$。在没有负权边的任意图（尤其是网格图、特殊构造的链状图或稠密图）中，出题人可以通过构造“卡 SPFA 数据”（如前向星加反向链或特殊长直链），使得队列中节点反复入队，引发拓扑震荡，算法直接退化为 Bellman-Ford 暴力搜索。

算法推导与状态设计

定义 $dist[u]$ 为源点 $s$ 到节点 $u$ 的当前最短路径估计值。

1. 三角形不等式与松弛操作（Relaxation）

对于任意边 $(u, v) \in E$，权值为 $w$。松弛操作是整个最短路径算法的核心状态转移方程：

$$dist[v] = \min(dist[v], dist[u] + w)$$

物理含义：判断从 $s$ 绕行 $u$ 到达 $v$ 的路径，是否比当前已知的直达或从其他途径到达 $v$ 的路径更短。

2. Dijkstra 堆优化状态设计

优先队列中存储的状态为二元组 $(d, u)$，其中 $u$ 为节点编号，$d$ 为当前的 $dist[u]$。二叉堆顶元素满足：

$$u_{\text{next}} = \arg\min_{v \in T} (dist[v])$$

由于 C++ std::priority_queue 默认是大根堆，在工程实现时必须重载结构体比较运算符，将其改造为小根堆。

C++ 标准源码（Dijkstra 堆优化标准工业模板）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const long long INF = 0x3f3f3f3f3f3f3f3fLL; // 使用足够大的长整型防止溢出
const int MAXN = 100005;

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

struct HeapNode {
    long long d;
    int u;
    // 致命低级错误防范：必须严格实现小根堆比较，否则大根堆会导致复杂度退化为暴力
    bool operator>(const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

std::vector<Edge> adj[MAXN];
long long dist[MAXN];
bool vis[MAXN]; // 标记是否已加入熟化集 S

void dijkstra(int s, int n) {
    // 状态初始化
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
        vis[i] = false;
    }

    // 声明小根堆
    std::priority_queue<HeapNode, std::vector<HeapNode>, std::greater<HeapNode> > pq;

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

    while (!pq.empty()) {
        HeapNode current = pq.top();
        pq.pop();

        int u = current.u;

        // 关键踩坑点：堆中可能存在旧的、更长距离的冗余节点，必须直接跳过
        if (vis[u]) continue; 
        vis[u] = true; // 正式并入熟化集 S

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            long long w = adj[u][i].weight;

            // 三角形不等式状态转移
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(HeapNode{dist[v], v});
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, s;
    if (!(std::cin >> n >> m >> s)) return 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        adj[u].push_back(Edge{v, w}); // 若为无向图需双向 push_back
    }

    dijkstra(s, n);

    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) {
            std::cout << 2147483647 << " "; // 对应部分真题要求的未到达输出值
        } else {
            std::cout << dist[i] << " ";
        }
    }
    std::cout << "\n";

    return 0;
}

NOIP 实战避坑指南

无脑迷信 SPFA 导致赛场直接被卡死： 部分选手由于习惯 SPFA 代码的简短或贪图其能处理负权的特性，在没有任何负权边的常规题中盲目选用 SPFA。近年来的 NOIP/省选评测中，凡是非负权单源最短路径题，出题人必定构造卡 SPFA 的特殊恶性数据。一旦选用 SPFA 相当于将 $O((V+E)\log V)$ 赌注押在 $O(VE)$ 的最坏结局上，直接导致 TLE 丢失 60% 以上的分数。在无负权边时，有且仅能使用 Dijkstra 堆优化。
堆优化中漏判 if (vis[u]) continue; 导致时间暴崩： 线性的松弛操作会导致同一个节点 $u$ 被多次更新并重复压入优先队列。如果不做 if (vis[u]) continue; 的懒惰删除判定，在面对稠密图时，出队节点会带有大量过期的脏数据并重新执行出边的 for 循环遍历，这会让优先队列的实际规模膨胀至 $O(E)$，算法时间复杂度直接退化，达不到预期的对数级优化效果。

经典 NOIP/洛谷真题

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

题意描述： 给定一个包含 $N$ 个点、$M$ 条有向边的带权图，求从源点 $S$ 出发到所有点的最短距离。数据满足 $N \le 10^5, M \le 2 \times 10^5$，边权非负。
问题本质与核心思路： 最纯净的非负权有向图单源最短路径问题。数据范围明确断绝了暴力 $O(V^2)$ Dijkstra 和 SPFA 的生路。核心思路是使用标准的 std::priority_queue 维护小根堆。每松弛成功一次，就将状态压入队列。出队时执行 vis 数组拦截，确保每条边只被松弛一次，每个节点只作为基准点扩张一次，属于必须闭眼无错写出的标杆代码。

2. 洛谷 P3003 [USACO10MAR] Grass Traveling G

题意描述： 给定一个由 $N$ 个点 $M$ 条双向边组成的无向非负权图。给出两个特定的目的地 $A$ 和 $B$，以及一个起点 $P$。要求设计一条路线，使得从 $P$ 出发，先到达 $A$ 再到达 $B$，或者先到达 $B$ 再到达 $A$ 的总行程距离最短。
问题本质与核心思路： 多起点单源最短路径的线性组合。无向图的距离具有对称性，即 $\text{dist}(A, B) = \text{dist}(B, A)$。从 $P$ 到 $A$ 再到 $B$ 的总距离为 $\text{dist}(P, A) + \text{dist}(A, B)$；先到 $B$ 再到 $A$ 的总距离为 $\text{dist}(P, B) + \text{dist}(B, A)$。问题的物理本质并不是要跑复杂的动态规划，而是分别以 $P$、$A$、$B$ 为源点，各跑一次标准的堆优化 Dijkstra 算法，得到三个单源最短路径距离向量。最终结果直接通过表达式 $\min(\text{dist}_P[A], \text{dist}_P[B]) + \text{dist}_A[B]$ 算出。时间复杂度为常数级放大的 $O(3 \times (V+E)\log V)$，依然极其高效。