C++ 中最短路算法的详细介绍（加强版）

C++ 中最短路算法的详细介绍

最短路算法是图论中的经典问题，旨在找到图中两个节点之间的边权和最小的路径。根据不同的需求和图的特点，有多种算法可以解决这一问题。本文将详细介绍几种常见的单源最短路算法，包括 Dijkstra 算法、Bellman-Ford 算法和 SPFA 算法，并提供相应的 C++ 实现代码。

---

一、Dijkstra 算法

引言

Dijkstra算法是一种著名的图论算法，用于解决单源最短路径问题。它是由荷兰计算机科学家Edsger W. Dijkstra在1956年提出的。

一、Dijkstra算法原理

1.1 核心思想

Dijkstra算法的核心思想是从起点开始，采用贪心策略，每次选择距离起点最近的节点进行扩展，直到扩展到终点或所有节点都被访问过。算法通过不断维护一个包含最短路径树中顶点的集合，逐步确定从起点到其他各顶点的最短路径。

1.2 基本步骤

• 初始化：将所有节点的最短路径估计值设为无穷大（INT_MAX），除起点外设为$0$。创建一个优先队列（最小堆），用于存储所有节点及其对应的最短路径估计值。同时，创建一个集合S用于记录已求出最短路径的顶点。

• 循环处理：重复以下步骤，直到优先队列为空或找到终点：

  • 从优先队列中取出最短距离估计值的节点u，并将其加入集合S。
  • 更新u的所有邻接顶点v的最短路径估计值。如果通过u到达v的路径比当前已知的路径更短，则更新v的估计值，并将其重新加入优先队列。

• 算法结束：当访问到终点时，算法结束。此时，终点的最短路径估计值即为从起点到终点的最短路径长度。

二、C++实现示例

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
using namespace std;// 定义图的邻接表表示
typedef pair<int, int> pii; // (顶点编号, 边权重)
vector<vector<pii>> graph; // 图的邻接表// dijkstra函数，使用优先队列优化
void dijkstra(int src, vector<int>& dist) {int V = graph.size();priority_queue<pii, vector<pii>, greater<pii>> pq; // 小顶堆pq.push({0, src}); // 起点到自己的距离为0dist[src] = 0;while (!pq.empty()) {int u = pq.top().second;int d = pq.top().first;pq.pop();// 如果当前节点的距离已经被更新过，跳过if (d > dist[u]) continue;// 遍历所有邻接点for (auto edge : graph[u]) {int v = edge.first;int w = edge.second;if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.push({dist[v], v});}}}
}int main() {// 初始化图int V = 5; // 顶点数graph.resize(V);// 添加边（无向图）graph[0].push_back({1, 10});graph[0].push_back({4, 3});graph[1].push_back({2, 1});graph[2].push_back({3, 4});graph[3].push_back({4, 2});graph[4].push_back({0, 3});graph[4].push_back({1, 1});graph[4].push_back({2, 8});graph[4].push_back({3, 2});// 计算最短路径vector<int> dist(V, INT_MAX);dijkstra(0, dist); // 从顶点0出发// 输出结果for (int i = 0; i < V; ++i) {cout << "从0到" << i << "的最短距离是：" << dist[i] << endl;}return 0;
}

三、代码详解

3.1 数据结构选择

• 邻接表：使用vector<vector<pii>>来存储图的邻接表，其中每个元素是一个pair，表示相邻顶点和边的权重。这种表示方法适合稀疏图，能够节省空间。

• 优先队列：使用priority_queue来实现最小堆，以便每次都能快速取出当前距离最小的节点。greater<pii>用于指定比较方式，使得优先队列按照边权重升序排列。

3.2 dijkstra函数解析

• 参数：src表示起点，dist是一个引用传递的向量，用于存储从起点到各顶点的最短距离。

• 初始化：将起点的距离设为$0$，并将起点加入优先队列。

• 主循环：不断从优先队列中取出距离最小的节点u，然后遍历其所有邻接点v。如果通过u到达v的路径比当前已知的路径更短，则更新v的距离，并将v加入优先队列。

• 剪枝优化：在取出节点u后，如果其当前距离大于之前记录的最短距离，说明该节点已经被处理过，可以直接跳过。这一步可以避免重复处理，提高效率。

3.3 main函数解析

• 图的构建：首先初始化图的顶点数和邻接表，然后添加边。这里假设是一个无向图，因此每条边需要添加两次。

• 调用dijkstra函数：从顶点$0$出发，计算其到其他所有顶点的最短距离。

• 结果输出：遍历dist向量，输出从起点到每个顶点的最短距离。

四、时间复杂度与适用场景

4.1 时间复杂度

• 标准实现：使用邻接矩阵和简单数组，时间复杂度为$O(n^2)$，其中$n$是顶点数。适用于小规模图。

• 优化实现：使用邻接表和优先队列（如上述C++代码），时间复杂度可以降低到$O((V+E){\log }_{2}V)$，其中$V$是顶点数，$E$是边数。适用于大规模稀疏图。

4.2 适用场景

• 路径规划：在地图应用中，为用户规划从起点到终点的最短行驶路径。

• 网络路由：在计算机网络中，寻找从源节点到目的节点的最优路由。

• 作业调度：在操作系统和数据库系统中，为作业分配资源，使总执行时间最短。

• 社交网络：在社交网络分析中，计算两个用户之间的最短关系路径。

• 通信网络：在通信网络设计中，计算信号从源点到目的地的最短传播路径。

需要注意的是，Dijkstra算法不适用于包含负权边的图。在这种情况下，可以使用Bellman-Ford算法来求解最短路径问题。

五、总结

Dijkstra算法作为一种高效的单源最短路径算法，在实际中有广泛的应用。通过合理的数据结构和优化策略，可以显著提高算法的性能。希望本文的介绍能够帮助您更好地理解和应用Dijkstra算法。

---

二、Bellman-Ford 算法

引言

在图论中，最短路径问题是一个经典且重要的问题。Bellman-Ford算法作为一种能够处理包含负权边的单源最短路径算法，具有独特的优势和应用场景。

一、Bellman-Ford算法原理

1.1 核心思想

Bellman-Ford算法的核心思想是通过对所有边进行多次松弛操作，逐步逼近从起点到其他各顶点的最短路径。与Dijkstra算法不同，Bellman-Ford算法允许边的权重为负数，并且能够检测图中是否存在负权回路。

1.2 基本步骤

1. 初始化：创建一个数组dist[]，用于存储从起点到各个顶点的最短路径长度。初始时，dist[s] = 0（其中s为起点），其余顶点的dist[]值设为无穷大（$INF$）。

2. 松弛操作：进行$V-1$轮松弛操作，其中$V$图中顶点的数量。在每一轮中，遍历图中的所有边$(u,v)$，如果通过u到达v的路径比当前已知的路径更短，则更新v的dist[]值。

3. 负权环检测：在完成上述$V-1$轮松弛操作后，再进行一轮松弛操作。如果在这一轮中仍然有某条边$(u,v)$满足dist[v] > dist[u] + w（w表示边$(u,v)$的权值），则说明图中存在一个负权回路。

1.3 时间复杂度

Bellman-Ford算法的时间复杂度为$O(V\times E)$，其中$V$是顶点数，$E$是边数。虽然这个复杂度比Dijkstra算法的$O((V+E){\log }_{2}V)$要高，但Bellman-Ford算法能够处理包含负权边的图，这是其独特的优势。

二、C++实现示例

#include <bits/stdc++.h>
using namespace std;const int INF = 0x3f3f3f3f;struct Edge {int from, to, weight;
};bool bellmanFord(int n, int m, int start, const vector<Edge>& edges, vector<int>& dist) {dist.assign(n + 1, INF);dist[start] = 0;// 进行 V - 1 轮松弛操作for (int i = 1; i <= n - 1; ++i) {bool updated = false;for (const auto& edge : edges) {int u = edge.from;int v = edge.to;int w = edge.weight;if (dist[u] != INF && dist[v] > dist[u] + w) {dist[v] = dist[u] + w;updated = true;}}if (!updated) break; // 如果没有任何更新，提前退出}// 检查负权回路for (const auto& edge : edges) {int u = edge.from;int v = edge.to;int w = edge.weight;if (dist[u] != INF && dist[v] > dist[u] + w) {return false; // 存在负权环}}return true; // 不存在负权环
}int main() {int n, m, start;cin >> n >> m >> start;vector<Edge> edges(m);for (int i = 0; i < m; ++i) {cin >> edges[i].from >> edges[i].to >> edges[i].weight;}vector<int> dist;if (bellmanFord(n, m, start, edges, dist)) {for (int i = 1; i <= n; ++i) {cout << "从" << start << "到" << i << "的最短距离是：" << dist[i] << endl;}} else {cout << "图中存在负权环" << endl;}return 0;
}

三、代码详解

3.1 数据结构选择

• Edge结构体：用于表示图中的边，包含起点from、终点to和权重weight。

• dist数组：用于存储从起点到各个顶点的最短路径长度。初始时，起点的距离设为$0$，其余顶点的距离设为无穷大（$INF$）。

3.2 bellmanFord函数解析

• 参数：n表示顶点数，m表示边数，start表示起点，edges是边的列表，dist是引用传递的向量，用于存储最短路径长度。

• 初始化：将dist数组初始化为$INF$，并将起点的距离设为$0$。

• 松弛操作：进行$n-1$轮松弛操作。在每一轮中，遍历所有边，如果通过当前边可以缩短路径，则更新dist数组。如果在某一轮中没有任何更新，则提前退出循环。

• 负权环检测：在完成$n-1$轮松弛操作后，再进行一轮松弛操作。如果在这一轮中仍然有边可以缩短路径，则说明图中存在负权环，返回false。否则，返回true。

3.3 main函数解析

• 输入处理：读取顶点数n、边数m和起点start，然后读取每条边的信息并存储在edges向量中。

• 调用bellmanFord函数：从起点start出发，计算其到其他所有顶点的最短距离。如果存在负权环，则输出提示信息；否则，输出从起点到每个顶点的最短距离。

四、适用场景与注意事项

4.1 适用场景

• 包含负权边的图：Bellman-Ford算法能够处理包含负权边的图，适用于需要求解单源最短路径且图中可能存在负权边的场景。

• 网络路由：在计算机网络中，寻找从源节点到目的节点的最优路由，尤其是在路由权重可能为负的情况下。

• 经济调度：在电力系统或生产调度中，计算成本最低的调度方案，其中某些调度操作可能具有负成本。

• 游戏开发：在路径规划中，考虑地形或其他因素导致的某些路径具有负权重，需要找到最优路径。

• 交通规划：在交通网络中，考虑不同路段的通行成本（如时间、费用等），其中某些路段可能因优惠或捷径而具有负权重。

4.2 注意事项

• 负权环检测：在使用Bellman-Ford算法时，需要确保图中不存在负权环，或者在算法中加入负权环检测机制。如果图中存在负权环，则算法会陷入无限循环，无法终止。

• 效率问题：Bellman-Ford算法的时间复杂度较高，对于大规模图来说，可能无法在合理时间内完成计算。在这种情况下，可以考虑使用SPFA算法等优化版本。

• 初始化：在初始化dist数组时，需要将起点的距离设为$0$，其余顶点的距离设为无穷大。这是算法正确运行的基础。

五、总结

Bellman-Ford算法作为一种经典的单源最短路径算法，具有能够处理包含负权边的图的独特优势。通过合理的实现和优化，可以在不同的应用场景中发挥重要作用。

---

三、SPFA 算法（队列优化的 Bellman-Ford）

引言

最短路问题是图论中的经典问题之一，广泛应用于交通导航、网络路由、游戏开发等领域。Dijkstra算法虽然高效，但无法处理包含负权边的图。针对这一问题，SPFA（Shortest Path Faster Algorithm）算法应运而生。

一、SPFA算法原理

1.1 核心思想

SPFA算法是对Bellman-Ford算法的一种优化，通过使用队列来减少不必要的松弛操作，从而提高算法效率。其核心思想是：只有那些距离值发生改变的节点，才有可能更新其邻接节点的距离值。因此，算法维护一个队列，用于存储待处理的节点。

1.2 基本步骤

1. 初始化：将所有节点的最短路径估计值设为无穷大（$INF$），起点的估计值设为$0$。创建一个空队列，并将起点加入队列。同时，创建一个布尔数组inQueue，用于记录节点是否在队列中。

2. 循环处理：重复以下步骤，直到队列为空：

   • 从队列中取出一个节点u，并将其标记为不在队列中。
   • 遍历u的所有邻接节点v，如果通过u到达v的路径比当前已知的路径更短，则更新v的估计值。如果v不在队列中，则将其加入队列。

3. 算法结束：当队列为空时，所有节点的最短路径都已确定。

1.3 负权环检测

SPFA算法还可以用于检测图中是否存在负权环。具体方法如下：

• 维护一个数组cnt，记录每个节点进入队列的次数。
• 如果在算法执行过程中，某个节点的cnt值超过节点总数n，则说明图中存在负权环。

二、C++实现示例

#include <bits/stdc++.h>
using namespace std;const int INF = 0x3f3f3f3f;
const int MAXN = 100010;struct Edge {int to, w, next;
} edge[MAXN];int head[MAXN], cnt;
int dist[MAXN], cntArr[MAXN];
bool inQueue[MAXN];
queue<int> q;void addEdge(int u, int v, int w) {edge[++cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt;
}bool spfa(int start, int n) {fill(dist, dist + n + 1, INF);dist[start] = 0;q.push(start);inQueue[start] = true;cntArr[start] = 1;while (!q.empty()) {int u = q.front();q.pop();inQueue[u] = false;for (int i = head[u]; i != 0; i = edge[i].next) {int v = edge[i].to;if (dist[v] > dist[u] + edge[i].w) {dist[v] = dist[u] + edge[i].w;if (!inQueue[v]) {q.push(v);inQueue[v] = true;cntArr[v]++;if (cntArr[v] > n) {return false; // 存在负权环}}}}}return true; // 不存在负权环
}int main() {int n, m, start;cin >> n >> m >> start;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;addEdge(u, v, w);}if (!spfa(start, n)) {cout << "存在负权环" << endl;} else {for (int i = 1; i <= n; ++i) {cout << "从" << start << "到" << i << "的最短距离是：" << dist[i] << endl;}}return 0;
}

三、代码详解

3.1 数据结构选择

• 邻接表：使用结构体Edge和数组head、edge来表示图的邻接表。这种方式适合稀疏图，能够节省空间。

• 队列：使用queue<int>来实现先进先出的队列，用于存储待处理的节点。

• 辅助数组：

  • dist[]：存储从起点到各节点的最短距离。
  • inQueue[]：记录节点是否在队列中，避免重复入队。
  • cntArr[]：记录每个节点进入队列的次数，用于检测负权环。

3.2 addEdge函数解析

• 功能：向图中添加一条边。

• 参数：u表示边的起点，v表示边的终点，w表示边的权重。

• 实现：将边的信息存储在edge数组中，并更新head数组，使其指向最新的边。

3.3 spfa函数解析

• 参数：start表示起点，n表示节点总数。

• 初始化：将所有节点的最短距离设为$INF$，起点的距离设为$0$。将起点加入队列，并标记为在队列中。

• 主循环：不断从队列中取出节点u，遍历其所有邻接节点v。如果通过u到达v的路径比当前已知的路径更短，则更新v的距离，并将v加入队列（前提是v不在队列中）。同时，更新cntArr[v]，如果某个节点的cntArr值超过n，则说明存在负权环，返回false。

• 算法结束：当队列为空时，返回true，表示不存在负权环。

3.4 main函数解析

• 输入处理：读取节点数n、边数m和起点start，然后读取每条边的信息并调用addEdge函数添加到图中。

• 调用spfa函数：从起点start出发，计算其到其他所有节点的最短距离。如果存在负权环，则输出提示信息；否则，输出从起点到每个节点的最短距离。

四、时间复杂度与适用场景

4.1 时间复杂度

• 平均情况：SPFA算法的时间复杂度为$O(k\times E)$，其中$k$是一个较小的常数，$E$是边的数量。在稀疏图中，$k$通常小于$2$，因此算法效率较高。

• 最坏情况：在存在负权环或稠密图中，SPFA算法的时间复杂度会退化到$O(V\times E)$，其中$V$是节点数，$E$是边数。这与Bellman-Ford算法相同。

4.2 适用场景

• 包含负权边的图：SPFA算法能够处理包含负权边的图，适用于需要求解单源最短路径且图中可能存在负权边的场景。

• 网络路由：在计算机网络中，寻找从源节点到目的节点的最优路由，尤其是在路由权重可能为负的情况下。

• 经济调度：在电力系统或生产调度中，计算成本最低的调度方案，其中某些调度操作可能具有负成本。

• 游戏开发：在路径规划中，考虑地形或其他因素导致的某些路径具有负权重，需要找到最优路径。

• 交通规划：在交通网络中，考虑不同路段的通行成本（如时间、费用等），其中某些路段可能因优惠或捷径而具有负权重。

需要注意的是，SPFA算法不适用于包含负权环的图。在这种情况下，算法会陷入无限循环，无法终止。因此，在使用SPFA算法时，需要确保图中不存在负权环，或者在算法中加入负权环检测机制。

五、总结

SPFA算法作为一种高效的单源最短路径算法，尤其适用于包含负权边的图。通过合理的数据结构和优化策略，可以显著提高算法的性能。

---

四、Floyd-Warshall 算法（多源最短路）

引言

在图论中，最短路径问题是一个经典且重要的问题。Floyd-Warshall算法作为一种能够处理包含负权边的多源最短路径算法，具有独特的优势和应用场景。

一、Floyd-Warshall算法原理

1.1 核心思想

Floyd-Warshall算法的核心思想是通过动态规划逐步寻找并更新所有顶点对之间的最短路径。算法使用一个距离矩阵来存储顶点之间的距离，并在每一步中考虑通过一个新的中间顶点来更新这些距离。

1.2 基本步骤

1. 初始化：创建一个大小为$n\times n$的距离矩阵dist[][]，其中dist[i][j]表示顶点i到顶点j的直接距离。如果i和j不直接相连，则dist[i][j]设为无穷大（$INF$）。同时，dist[i][i]设为$0$，表示自己到自己的距离为$0$。

2. 中间节点迭代：依次枚举每一个顶点k，将顶点k加入中转点考虑，更新距离矩阵dist[][]。具体来说，对于每一对顶点$(i,j)$，如果通过中转点k可以得到更短的距离，即dist[i][j] > dist[i][k] + dist[k][j]，则更新dist[i][j]为dist[i][k] + dist[k][j]。

3. 输出结果：在完成所有中间节点的迭代后，距离矩阵dist[][]中的值即为任意两个顶点之间的最短路径长度。

1.3 时间复杂度

Floyd-Warshall算法的时间复杂度为$O(n^3)$，其中n是图中顶点的数量。由于其时间复杂度较高，对于大规模图来说，可能无法在合理时间内完成计算。因此，该算法适用于小规模稠密图。

二、C++实现示例

#include <bits/stdc++.h>
using namespace std;const int INF = numeric_limits<int>::max();void floydWarshall(vector<vector<int>>& dist, int n) {// 中间节点迭代for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// 如果通过顶点k可以找到更短的路径，则更新dist[i][j]if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}
}int main() {int n, m;cin >> n >> m; // 输入顶点数和边数vector<vector<int>> dist(n, vector<int>(n, INF));// 初始化距离矩阵for (int i = 0; i < n; i++) {dist[i][i] = 0;}// 输入边的信息for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;dist[u][v] = w;}// 调用Floyd-Warshall算法floydWarshall(dist, n);// 输出最短距离矩阵cout << "每对顶点间的最短距离：" << endl;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][j] == INF) {cout << "INF ";} else {cout << dist[i][j] << " ";}}cout << endl;}return 0;
}

三、代码详解

3.1 数据结构选择

• 距离矩阵：使用二维向量dist[][]来存储顶点之间的距离。初始时，所有顶点对之间的距离设为无穷大（$INF$），除了自己到自己的距离设为$0$。

3.2 floydWarshall函数解析

• 参数：dist是引用传递的距离矩阵，n是顶点数。

• 中间节点迭代：通过三层循环遍历所有可能的中间节点k、起点i和终点j。如果通过k可以找到更短的路径，则更新dist[i][j]。

3.3 main函数解析

• 输入处理：读取顶点数n和边数m，然后读取每条边的信息并存储在距离矩阵dist[][]中。

• 调用floydWarshall函数：计算所有顶点对之间的最短路径。

• 输出结果：输出最短距离矩阵，其中INF表示两个顶点之间没有路径。

四、适用场景与注意事项

4.1 适用场景

• 多源最短路径问题：Floyd-Warshall算法能够计算图中所有顶点对之间的最短路径，适用于需要求解多源最短路径的场景。

• 包含负权边的图：该算法能够处理包含负权边的图，但图中不能有负权环，否则最短路径问题没有解。

• 小规模稠密图：由于其时间复杂度较高，Floyd-Warshall算法适用于小规模稠密图。对于大规模稀疏图，可以考虑使用其他算法如Dijkstra或SPFA。

4.2 注意事项

• 负权环检测：在使用Floyd-Warshall算法时，需要确保图中不存在负权环。如果图中存在负权环，则算法会陷入无限循环，无法终止。因此，在实际使用中，需要先检测图中是否存在负权环。

• 初始化：在初始化距离矩阵时，需要将所有顶点对之间的距离设为无穷大（INF），除了自己到自己的距离设为$0$。这是算法正确运行的基础。

• 空间复杂度：Floyd-Warshall算法的空间复杂度为$O(n^2)$，需要存储一个$n\times n$的距离矩阵。对于大规模图来说，这可能会占用较多的内存。

五、总结

Floyd-Warshall算法作为一种经典的多源最短路径算法，具有能够处理包含负权边的图的独特优势。通过合理的实现和优化，可以在不同的应用场景中发挥重要作用。