求单源最短路(Dijkstra 算法-迪杰斯特拉算法，SPFA)

求单源最短路径的两个非常重要的算法：Dijkstra 算法和 SPFA 算法。我会用通俗易懂的方式讲解它们的核心思想、步骤、区别，并提供经典的 C++ 代码实现。

Dijkstra 算法 (迪杰斯特拉算法)

Dijkstra 是图论算法中名气最大、也最经典的算法之一。它专门用来解决无负权边图的单源最短路径问题。

核心思想

Dijkstra 的核心是贪心策略。它将所有顶点分为两类：

1. 已确定最短路径的顶点集合 (S)
2. 未确定最短路径的顶点集合 (U)

算法的每一步都是从集合 U 中，找出一个距离源点 start 最近的顶点 u，然后将 u 加入到集合 S 中。接着，以 u 为中介，去更新 u 的所有邻居到源点的距离（这个过程称为“松弛”）。重复这个过程，直到所有顶点都加入到集合 S 中。

算法比喻

想象一场森林大火，源点 start 是第一个着火点。

• dist[i] 表示火势蔓延到树 i 的最早时间。
• Dijkstra 算法的每一步，都是在所有“尚未烧起来、但已经被火星溅到”的树中，选择那棵最快会烧起来的树（距离源点最近的）。
• 当这棵树 u 正式开始燃烧时，它会立刻向它的邻居 v 溅射火星。如果从 u 这里传过去的火星能让 v 更早地着火（即 dist[u] + weight(u,v) < dist[v]），那么我们就更新 v 的预计着火时间 dist[v]。
• 因为火势蔓延的时间（边的权重）总是正的，所以一旦一棵树烧起来了，它的着火时间就确定了，不可能再被一个更晚烧起来的树更新为一个更早的时间。这就是 Dijkstra 贪心策略正确的根基。

算法步骤

1. 初始化：
   • 创建一个距离数组 dist，dist[i] 表示从源点 start 到顶点 i 的临时最短距离。初始化 dist[start] = 0，其他所有 dist[i] = ∞。
   • 创建一个优先队列（最小堆），并将 (0, start)（距离, 顶点编号）放入队列。
2. 循环：
   • 当优先队列不为空时，取出堆顶元素 (d, u)，即当前 dist 值最小的顶点。
   • 如果顶点 u 已经被访问过（或者当前取出的距离 d 大于 dist[u]，说明这是一个过时的、较长的路径），则跳过。
   • 标记 u 为已访问。
   • 松弛操作：遍历 u 的所有邻居 v。如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v] = dist[u] + weight(u, v)，并将新的 (dist[v], v) 压入优先队列。
3. 结束：当优先队列为空时，dist 数组中就存储了从源点 start 到所有其他顶点的最短路径长度。

C++ 代码实现 (优先队列优化版)

这是面试和竞赛中最常用、效率最高的版本。

#include <iostream>
#include <vector>
#include <queue>
#include <limits>using namespace std;// 使用 pair 来存储 {邻接点, 边权重}
using Edge = pair<int, int>; 
// 使用 pair 来存储 {距离, 顶点}，方便优先队列排序
using State = pair<int, int>; const int INF = numeric_limits<int>::max();// V: 顶点数, adj: 邻接表, start: 源点
vector<int> dijkstra(int V, const vector<vector<Edge>>& adj, int start) {// 1. 初始化vector<int> dist(V, INF);dist[start] = 0;// 优先队列，存储 {距离, 顶点}。默认是最大堆，需要用 greater<> 转换成最小堆priority_queue<State, vector<State>, greater<State>> pq;pq.push({0, start});// 2. 循环while (!pq.empty()) {// 取出当前距离最小的顶点State current = pq.top();pq.pop();int d = current.first;int u = current.second;// 这是一个重要的优化：如果当前取出的距离比已经记录的还要大，// 说明这是一个旧的、更长的路径信息，直接跳过。if (d > dist[u]) {continue;}// 3. 松弛操作for (const auto& edge : adj[u]) {int v = edge.first;int weight = edge.second;if (dist[u] != INF && dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;pq.push({dist[v], v});}}}return dist;
}int main() {int V = 6; // 顶点数 (0 to 5)vector<vector<Edge>> adj(V);// 构建一个有向图// addEdge(u, v, weight)adj[0].push_back({1, 5});adj[0].push_back({2, 1});adj[1].push_back({3, 3});adj[1].push_back({4, 20});adj[2].push_back({1, 3});adj[2].push_back({4, 12});adj[3].push_back({2, 3});adj[3].push_back({4, 2});adj[3].push_back({5, 6});adj[4].push_back({5, 1});int start_node = 0;vector<int> result = dijkstra(V, adj, start_node);cout << "Dijkstra's Algorithm Results:" << endl;cout << "Shortest distances from node " << start_node << ":" << endl;for (int i = 0; i < V; ++i) {cout << "  Node " << i << ": ";if (result[i] == INF) {cout << "Infinity" << endl;} else {cout << result[i] << endl;}}// 预期输出: 0: 0, 1: 4, 2: 1, 3: 7, 4: 9, 5: 10return 0;
}

• 时间复杂度：$O(E\log V)$，其中 E 是边数，V 是顶点数。每个顶点和每条边最多入队一次，优先队列的操作是 $\log V$ 级别的。
• 空间复杂度：$O(V+E)$，用于存储邻接表、距离数组和优先队列。

SPFA 算法 (Shortest Path Faster Algorithm)

SPFA 算法实际上是 Bellman-Ford 算法的队列优化版本。它和 Dijkstra 最大的不同在于，它可以处理带有负权边的图，并且可以检测负权环。

核心思想

Bellman-Ford 算法会盲目地对所有边进行 V-1 轮松弛。SPFA 认为这是没有必要的，只有那些刚刚被松弛过的顶点，才有可能去松弛它的邻居。

所以，SPFA 使用一个队列来维护这些“刚刚被松弛过”的顶点。每次从队列中取出一个顶点 u，并用它去松弛它的所有邻居 v。如果某个邻居 v 被成功松弛了，并且 v 当前不在队列中，就将 v 加入队列。这个过程一直持续到队列为空。

算法比喻

可以把 SPFA 想象成一个“流言传播”模型，源点是第一个知道流言的人。

• dist[i] 表示流言传到 i 耳中的“失真度”（可以为负）。
• 当某个人 u 听到了一个“失真度”更低的流言版本时（dist[u] 变小），他会很兴奋地把他知道的版本告诉他所有的朋友 v。
• 如果他的朋友 v 听到的版本比自己之前听到的版本“失真度”更低，v 也会被“激活”，加入到准备传播流言的队列中，再去告诉他的朋友们。
• 负权环检测：如果这个图中存在一个“流言怪圈”（负权环），大家会不停地互相更新，流言的失真度会无限降低。SPFA 通过记录每个顶点入队的次数来检测这种情况，如果一个顶点入队次数超过了总顶点数 V，就说明存在负权环。

算法步骤

1. 初始化：
   • 创建一个距离数组 dist，初始化 dist[start] = 0，其他 dist[i] = ∞。
   • 创建一个队列 q，并将源点 start 入队。
   • 创建一个布尔数组 in_queue，标记顶点是否在队列中，in_queue[start] = true。
   • 创建一个计数数组 count，count[i] 记录顶点 i 的入队次数，count[start] = 1。
2. 循环：
   • 当队列 q 不为空时，取出队首元素 u。
   • 将 in_queue[u] 设为 false。
   • 松弛操作：遍历 u 的所有邻居 v。如果 dist[u] + weight(u, v) < dist[v]：
     • 更新 dist[v] = dist[u] + weight(u, v)。
     • 如果 v 不在队列中，则将 v 入队，in_queue[v] 设为 true，并增加 count[v]。
     • 负权环检测：如果 count[v] 大于等于 V（顶点数），说明存在负权环，算法返回失败。
3. 结束：如果算法正常结束（队列为空），则 dist 数组即为最短路径结果。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <limits>using namespace std;using Edge = pair<int, int>;
const int INF = numeric_limits<int>::max();// V: 顶点数, adj: 邻接表, start: 源点
// 返回一个 pair, bool 表示是否成功 (无负权环), vector<int> 是距离数组
pair<bool, vector<int>> spfa(int V, const vector<vector<Edge>>& adj, int start) {// 1. 初始化vector<int> dist(V, INF);vector<int> count(V, 0); // 记录入队次数vector<bool> in_queue(V, false);queue<int> q;dist[start] = 0;q.push(start);in_queue[start] = true;count[start]++;// 2. 循环while (!q.empty()) {int u = q.front();q.pop();in_queue[u] = false;// 3. 松弛操作for (const auto& edge : adj[u]) {int v = edge.first;int weight = edge.second;if (dist[u] != INF && dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;if (!in_queue[v]) {q.push(v);in_queue[v] = true;count[v]++;// 4. 负权环检测if (count[v] >= V) {return {false, {}}; // 检测到负权环}}}}}return {true, dist}; // 成功找到最短路径
}int main() {int V = 5; // 顶点数 (0 to 4)vector<vector<Edge>> adj(V);// 构建一个带负权边的图adj[0].push_back({1, 6});adj[0].push_back({2, 7});adj[1].push_back({3, 5});adj[1].push_back({4, -4});adj[2].push_back({3, -2});adj[3].push_back({1, -2});adj[4].push_back({0, 1}); // 这条边可能构成负权环，但此例中不会int start_node = 0;auto result_pair = spfa(V, adj, start_node);cout << "SPFA Algorithm Results:" << endl;if (result_pair.first) {cout << "Shortest distances from node " << start_node << ":" << endl;vector<int> result = result_pair.second;for (int i = 0; i < V; ++i) {cout << "  Node " << i << ": ";if (result[i] == INF) {cout << "Infinity" << endl;} else {cout << result[i] << endl;}}// 预期输出: 0: 0, 1: 2, 2: 7, 3: 5, 4: -2} else {cout << "Negative cycle detected!" << endl;}// 负权环例子cout << "\n--- Testing with a negative cycle ---" << endl;vector<vector<Edge>> adj_cycle(3);adj_cycle[0].push_back({1, 1});adj_cycle[1].push_back({2, 1});adj_cycle[2].push_back({0, -3}); // 1+1-3 = -1 < 0, 构成负权环auto cycle_result = spfa(3, adj_cycle, 0);if (!cycle_result.first) {cout << "Negative cycle detected!" << endl;}return 0;
}

• 时间复杂度：
  • 平均情况：$O(kE)$，其中 k 是一个小的常数，对于稀疏图，效率很高，接近 $O(E)$。
  • 最坏情况：$O(V\cdot E)$，与 Bellman-Ford 相同。在一些特殊构造的网格图上，SPFA 的性能会退化到最坏情况，因此在一些算法竞赛中可能会被“卡”。
• 空间复杂度：$O(V+E)$。

Dijkstra vs. SPFA 总结

面试/机试建议：

1. 首选 Dijkstra：如果题目明确说明或可以推断出所有边的权重都是非负的，那么一定要用 Dijkstra。它的性能更稳定，且不会被特殊数据卡到最坏情况。
2. 备用 SPFA：当题目中出现了负权边时，才考虑使用 SPFA。你需要清楚地知道它的优点（能处理负权）和缺点（最坏情况下的性能）。
3. 在 LeetCode 和大多数公司机试中，Dijkstra 的出场率远高于 SPFA。务必将 Dijkstra 的代码模板烂熟于心。