当前位置: 首页 > news >正文

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

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

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

一、Dijkstra 算法

1. 算法概述

Dijkstra 算法是由荷兰计算机科学家艾兹格·迪科斯彻(Edsger W. Dijkstra)在 1959 年提出的,用于计算单源最短路径。该算法适用于边权非负的有向图或无向图。

2. 算法原理

Dijkstra 算法的核心思想是贪心策略,通过不断选择当前未处理节点中距离起点最近的节点,逐步扩展到所有节点。具体步骤如下:

  1. 初始化:设置起点到自身的距离为 000,其他节点的距离为无穷大(INFINFINF)。
  2. 选择最小距离节点:从未处理的节点中选择距离起点最近的节点 u
  3. 更新邻接节点:遍历节点 u 的所有邻接节点 v,如果通过 uv 的距离比当前记录的距离更短,则更新 v 的距离。
  4. 标记已处理:将节点 u 标记为已处理。
  5. 重复:重复步骤 2-4,直到所有节点都被处理。

3. C++ 实现

以下是 Dijkstra 算法的两种实现方式:朴素版和使用优先队列优化版。

3.1 朴素版 Dijkstra
#include <bits/stdc++.h>
using namespace std;const int N = 1005, INF = 1e9;
int n, m; // 节点数和边数
int d[N]; // 存储起点到各点的最短距离
bool st[N]; // 标记节点是否已处理
vector<pair<int, int>> adj[N]; // 邻接表表示图void dijkstra(int s) {fill(d, d + N, INF);d[s] = 0;for(int i = 1; i <= n; i++) {int u = -1;for(int j = 1; j <= n; j++) {if(!st[j] && (u == -1 || d[j] < d[u])) {u = j;}}if(u == -1) break;st[u] = true;for(auto [v, w] : adj[u]) {if(d[v] > d[u] + w) {d[v] = d[u] + w;}}}
}int main(){cin >> n >> m;for(int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;adj[a].emplace_back(b, c);// 如果是无向图,取消下面的注释// adj[b].emplace_back(a, c);}dijkstra(1); // 假设起点是1for(int i = 1; i <= n; i++) {cout << "从1到" << i << "的最短路为" << d[i] << endl;}return 0;
}
3.2 使用优先队列优化的 Dijkstra

为了优化时间复杂度,可以使用优先队列(堆)来快速选择当前距离起点最近的节点。这样可以将时间复杂度从 O(n2)O(n^2)O(n2) 降低到 O((n+m)log⁡2n)O((n + m)\log_2 n)O((n+m)log2n)

#include <bits/stdc++.h>
using namespace std;const int N = 1005, INF = 1e9;
int n, m; // 节点数和边数
int d[N]; // 存储起点到各点的最短距离
bool st[N]; // 标记节点是否已处理
vector<pair<int, int>> adj[N]; // 邻接表表示图void dijkstra(int s) {fill(d, d + N, INF);d[s] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> pq;pq.emplace(0, s);while(!pq.empty()){auto [dist, u] = pq.top(); pq.pop();if(st[u]) continue;st[u] = true;for(auto [v, w] : adj[u]){if(d[v] > d[u] + w){d[v] = d[u] + w;pq.emplace(d[v], v);}}}
}int main(){cin >> n >> m;for(int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;adj[a].emplace_back(b, c);// 如果是无向图,取消下面的注释// adj[b].emplace_back(a, c);}dijkstra(1); // 假设起点是1for(int i = 1; i <= n; i++) {cout << "从1到" << i << "的最短路为" << d[i] << endl;}return 0;
}

4. 适用场景与注意事项

  • 边权非负:Dijkstra 算法要求所有边的权重为非负数。如果存在负权边,算法可能无法正确工作。
  • 稀疏图与稠密图:对于稀疏图(边数远小于 n2n^2n2),使用优先队列优化的 Dijkstra 效率较高;对于稠密图,可以考虑使用 Floyd-Warshall 算法。
  • 单源最短路径:Dijkstra 算法用于计算单源最短路径,即从一个起点到所有其他节点的最短路径。

二、Bellman-Ford 算法

1. 算法概述

Bellman-Ford 算法由 Robert Floyd 在 1956 年提出,用于计算单源最短路径。与 Dijkstra 算法不同,Bellman-Ford 算法能够处理含有负权边的图,但不适用于含有负权环的图。

2. 算法原理

Bellman-Ford 算法的核心思想是通过对所有边进行多次松弛操作,逐步逼近最短路径。具体步骤如下:

  1. 初始化:设置起点到自身的距离为 000,其他节点的距离为无穷大(INFINFINF)。
  2. 松弛操作:对图中的所有边进行 n−1n-1n1 次松弛操作,其中 nnn 是节点数。每次松弛操作尝试通过当前边缩短起点到终点的距离。
  3. 检测负权环:再进行一次松弛操作,如果仍有距离被更新,说明图中存在负权环。

3. C++ 实现

#include <bits/stdc++.h>
using namespace std;const int N = 1005, INF = 1e9;
int n, m; // 节点数和边数
int d[N]; // 存储起点到各点的最短距离
vector<tuple<int, int, int>> edges; // 存储所有边 (u, v, w)bool bellman_ford(int s) {fill(d, d + N, INF);d[s] = 0;// 进行 n-1 次松弛操作for(int i = 1; i < n; i++) {for(auto [u, v, w] : edges) {if(d[v] > d[u] + w) {d[v] = d[u] + w;}}}// 检测负权环for(auto [u, v, w] : edges) {if(d[v] > d[u] + w) {return false; // 存在负权环}}return true; // 不存在负权环
}int main(){cin >> n >> m;for(int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;edges.emplace_back(a, b, c);}if(bellman_ford(1)) { // 假设起点是1for(int i = 1; i <= n; i++) {cout << "从1到" << i << "的最短路为" << d[i] << endl;}} else {cout << "图中包含负环" << endl;}return 0;
}

4. 适用场景与注意事项

  • 处理负权边:Bellman-Ford 算法能够正确处理含有负权边的图。
  • 检测负权环:如果在 n−1n-1n1 次松弛后,仍能通过某条边缩短距离,说明图中存在负权环。
  • 时间复杂度:Bellman-Ford 算法的时间复杂度为 O(nm)O(nm)O(nm),在边数较多时效率较低。
  • 不适用于含有负权环的图:如果图中存在负权环,算法无法正确计算最短路径。

三、SPFA 算法(队列优化的 Bellman-Ford)

1. 算法概述

SPFA(Shortest Path Faster Algorithm)是一种对 Bellman-Ford 算法的改进,通过使用队列来优化松弛操作的顺序,从而提高算法效率。SPFA 通常比 Bellman-Ford 更快,但在最坏情况下时间复杂度仍为 O(nm)O(nm)O(nm)

2. 算法原理

SPFA 算法的核心思想是动态逼近最短路径,通过队列来维护需要松弛的节点。具体步骤如下:

  1. 初始化:设置起点到自身的距离为 000,其他节点的距离为无穷大(INFINFINF)。将起点加入队列。
  2. 松弛操作:从队列中取出一个节点 u,遍历其所有邻接节点 v,如果通过 uv 的距离比当前记录的距离更短,则更新 v 的距离,并将 v 加入队列(如果 v 不在队列中)。
  3. 重复:重复步骤 2,直到队列为空。
  4. 检测负权环:如果某个节点被松弛的次数超过 n−1n-1n1 次,说明图中存在负权环。

3. C++ 实现

#include <bits/stdc++.h>
using namespace std;const int N = 1005, INF = 1e9;
int n, m; // 节点数和边数
int d[N]; // 存储起点到各点的最短距离
int cnt[N]; // 记录每个节点被松弛的次数
vector<pair<int, int>> adj[N]; // 邻接表表示图
bool in_queue[N]; // 标记节点是否在队列中
queue<int> q; // 队列用于SPFAbool spfa(int s) {fill(d, d + N, INF);d[s] = 0;q.push(s);in_queue[s] = true;cnt[s] = 1;while(!q.empty()){int u = q.front(); q.pop();in_queue[u] = false;for(auto [v, w] : adj[u]){if(d[v] > d[u] + w){d[v] = d[u] + w;if(!in_queue[v]){q.push(v);in_queue[v] = true;cnt[v]++;if(cnt[v] > n) return false; // 存在负权环}}}}return true; // 不存在负权环
}int main(){cin >> n >> m;for(int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;adj[a].emplace_back(b, c);// 如果是无向图,取消下面的注释// adj[b].emplace_back(a, c);}if(spfa(1)) { // 假设起点是1for(int i = 1; i <= n; i++) {cout << "从1到" << i << "的最短路为" << d[i] << endl;}} else {cout << "图中包含负环" << endl;}return 0;
}

4. 适用场景与注意事项

  • 处理负权边:SPFA 算法能够正确处理含有负权边的图。
  • 检测负权环:通过记录每个节点被松弛的次数,可以检测图中是否存在负权环。
  • 平均时间复杂度较低:在一般情况下,SPFA 的平均时间复杂度比 Bellman-Ford 低,但最坏情况下仍为 O(nm)O(nm)O(nm)
  • 不保证最优性:在某些特殊情况下,SPFA 可能无法得到最优解,需要结合具体问题进行分析。

四、Floyd-Warshall 算法(多源最短路)

1. 算法概述

Floyd-Warshall 算法由 Robert Floyd 在 1962 年提出,用于计算图中所有节点对之间的最短路径。该算法适用于含有正权和负权边的有向图或无向图,但不适用于含有负权环的图。

2. 算法原理

Floyd-Warshall 算法基于动态规划的思想,通过枚举中间节点 k,逐步更新所有节点对之间的最短路径。具体步骤如下:

  1. 初始化:创建一个二维数组 d,其中 d[i][j] 表示节点 i 到节点 j 的最短距离。初始时,d[i][j] 为节点 i 到节点 j 的直接边的权重,如果没有直接边,则设为无穷大(INFINFINF)。对角线上的元素 d[i][i] 设为 000
  2. 动态规划:对于每个中间节点 k,遍历所有节点对 (i, j),如果通过 k 可以缩短 ij 的距离,则更新 d[i][j]
  3. 结果:最终,d[i][j] 将包含节点 i 到节点 j 的最短距离。如果 d[i][j] 仍为无穷大,说明 i 无法到达 j

3. C++ 实现

#include <bits/stdc++.h>
using namespace std;const int N = 105, INF = 1e9;
int n, m; // 节点数和边数
int d[N][N]; // 存储最短距离矩阵void floyd(){// 初始化距离矩阵for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(i == j) d[i][j] = 0;else d[i][j] = INF;}}// 读取边并更新距离矩阵for(int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;d[a][b] = min(d[a][b], c);// 如果是无向图,取消下面的注释// d[b][a] = min(d[b][a], c);}// Floyd-Warshall算法核心部分for(int k = 1; k <= n; k++) {for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(d[i][k] + d[k][j] < d[i][j]) {d[i][j] = d[i][k] + d[k][j];}}}}
}int main(){cin >> n >> m;floyd();// 输出所有节点对的最短距离for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(d[i][j] == INF) cout << "INF ";else cout << d[i][j] << " ";}cout << endl;}return 0;
}

4. 适用场景与注意事项

  • 处理负权边:Floyd-Warshall 算法能够正确处理含有负权边的图。
  • 检测负权环:Floyd-Warshall 算法可以检测图中是否存在负权环。
  • 时间复杂度较高:在密集图中,即边数接近顶点数平方的情况下,Floyd-Warshall算法的效率相对较高。但该算法的时间复杂度为O(n3)O(n^3)O(n3),其中n是图中顶点的数量。因此,在处理大规模图时,可能会遇到性能问题。
  • 空间复杂度较高:算法的空间复杂度为O(n2)O(n^2)O(n2),需要存储一个n×nn\times nn×n的距离矩阵。在内存受限的环境中,这可能成为一个考虑因素。
  • 不适用于含有负权环的图:如果图中存在负权环,Floyd-Warshall 算法无法正确计算最短路径。在这种情况下,可以考虑使用其他算法,如Bellman-Ford算法。
http://www.lryc.cn/news/583542.html

相关文章:

  • JAVA策略模式demo【设计模式系列】
  • LaCo: Large Language Model Pruning via Layer Collapse
  • Java 大视界 -- 基于 Java 的大数据分布式计算在生物信息学蛋白质 - 蛋白质相互作用预测中的应用(340)
  • windows指定某node及npm版本下载
  • Using Spring for Apache Pulsar:Message Production
  • Softmax函数的学习
  • 矩阵之方阵与行列式的关系
  • Flink-1.19.0源码详解6-JobGraph生成-后篇
  • Android Soundtrigger唤醒相关时序学习梳理
  • 常见 HTTP 方法的成功状态码200,204,202,201
  • C++并发编程-11. C++ 原子操作和内存模型
  • Token 和 Embedding的关系
  • 通过Tcl脚本命令:set_param labtools.auto_update_hardware 0
  • AI Agent:我的第一个Agent项目
  • 在 macOS 上安装与自定义 Oh My Zsh:让终端美观又高效 [特殊字符]
  • css支持if else
  • WIndows 编程辅助技能:格式工厂的使用
  • 单片机STM32F103:DMA的原理以及应用
  • React面试高频考点解析
  • 【LeetCode 热题 100】21. 合并两个有序链表——(解法二)递归法
  • Spark流水线数据对比组件
  • 第6章应用题
  • 01-elasticsearch-搭个简单的window服务-ik分词器-简单使用
  • 【01】MFC入门到精通—— MFC新建基于对话框的项目 介绍(工作界面、资源视图 、类视图)
  • 【前端】ikun-markdown: 纯js实现markdown到富文本html的转换库
  • Java SE 实现简单的图书管理系统(完善菜单操作)
  • 【DOCKER】-3 数据持久化
  • 项目进度受制于资源分配,如何动态调配资源
  • 20250709: WSL+Pycharm 搭建 Python 开发环境
  • PHP 基于模板动态生成 Word 文档:图片 + 表格数据填充全方案(PHPOffice 实战)