当前位置： 首页 > article >正文

最短路问题

article 2025/3/1 3:37:32

如何建图？

对于大多数初学者来说如何建图是一个比较头疼的问题？下面讲解两种用的比较多的建图思路！

邻接矩阵

邻接矩阵是最简单的建图方式之一，它的思路就是初始化一个二维矩阵，(i, j) 就表示从顶点 i 走到顶点 j：

  • 对于不带权值的图来说，g[i][j] = INF（INF为无穷大的一个数）说明点 i 和点 j 之间不存在边，g[i][j] = 1 表示点 i 和 点 j 之间存在一条边或者路径
  • 对于带权图来说，g[i][j] = INF 说明点 i 和点 j 之间不存在边，g[i][j] = w 表示点 i 和 点 j 之间的权值（可以理解为两个点之间的路径距离）

因此，对于 n 个顶点 m 条边有建图代码如下：

cin >> n >> m;
for (int i = 1; i <= m; i++){
	int x, y, z; // 点x、y之间的权值为z
	cin >> x >> y >> z;
	g[x][y] = min(z, g[x][y]); // 有向图
}

邻接矩阵多用于稠密图，即边比较多的时候（如果是稀疏图的话有大量的0导致空间浪费）

链式前向星

链式前向星（Chained Forward Star）是一种用于表示稀疏图的数据结构。它主要用于解决图论中的一些算法问题，如最短路径、最小生成树等。

链式前向星通过两个数组来表示图的边和顶点信息：

  1. 边数组（Edge Array）：存储了每条边的相关信息，如起点、终点、权重等。
  2. 下一个边数组（Next Edge Array）：存储了每个顶点的第一条出发边的索引值，通过这个数组可以找到下一条以同一起点的边。

链式前向星的优势在于它能够高效地处理稀疏图，节省了存储空间，并且能够在常数时间内访问某个顶点的所有出发边。

// h存放的是每个顶点出发的边
// e存放的是每条边到达的目的地
// w存放的是权值
// ne存放的是当前顶点下一条边的序号
// idx存放的当前的边的序号
int h[N], e[N], w[N], ne[N], idx; // 链式前向星

void add(int x, int y, int z){ // 从顶点x到顶点y，边的权值为z
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}

Dijkstra朴素版

迪杰斯特拉是一种贪心策略的算法。

其思路在于每次选取一个离源点最近距离的顶点去更新到其他点的距离。

题目描述：

  • 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
  • 请你求出 1 1 1 号点到 n n n 号点的最短距离，如果无法从 1 1 1 号点走到 n n n 号点，则输出 − 1 −1 −1。
  • 1 ≤ n ≤ 500 1≤n≤500 1≤n≤500、 1 ≤ m ≤ 1 0 5 1≤m≤10^5 1≤m≤105、图中涉及边长均不超过 10000 10000 10000。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 505;
int n, m, x, y, z;
int g[N][N], dist[N]; // dist为从源点到其他顶点的距离
bool st[N];

void Dijkstra(){
	// 每次选择离源点最近，一共有n个顶点，因此要循环n次
	for (int i = 1; i <= n; i++){
		int t = -1;
		for (int j = 1; j <= n; j++){
			if(!st[j] && (t == -1 || dist[j] < dist[t])) // 找当前最短路径的点
				t = j;
		}
		st[t] = true;
		for (int j = 1; j <= n; j++){
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
}

int main(){
	memset(g, 0x3f, sizeof g); // 初始化邻接矩阵为0x3f3f3f3f
	memset(dist, 0x3f, sizeof dist); // 初始化dist数组为0x3f3f3f3f
	cin >> n >> m;
	while(m--){
		cin >> x >> y >> z;
		g[x][y] = min(z, g[x][y]); // 防止两个顶点出现多条边的情况
	}
	dist[1] = 0;
	Dijkstra();
	cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]) << endl;
	return 0;
}

为什么要初始化为 0 x 3 f 3 f 3 f 3 f 0x3f3f3f3f 0x3f3f3f3f 呢？

  • 第一个原因就是 0 x 3 f 3 f 3 f 3 f 0x3f3f3f3f 0x3f3f3f3f 已经是一个很大的数据了，可以用它来表示无穷大
  • 第二个原因就是 0 x 3 f 3 f 3 f 3 f 0x3f3f3f3f 0x3f3f3f3f 在进行运算的时候也不会爆范围

朴素版 Dijkstra 算法适用于稠密图

Dijkstra堆优化版

Dijkstra 堆优化版本是在朴素版上进行了升级，在朴素版本中每次找最短距离的顶点是借助 for 去查找的，在堆优化版本中我们使用小根堆去存储距离，用小根堆存放每个顶点到源点的距离，它会自动根据距离自动进行排序，因此，在对头就是距离最短的点，每次就从队头取元素。同时还需要存顶点的编号，因此存放的是一个 pair，它包含了距离和对应订单编号的信息。

C++中小根堆（也叫优先队列）怎么建立呢？

// 默认建立的是大根堆，加入greater表示小根堆
priority_queue<int, vector<int>, greater<int>> q;     //小根堆  3 2 1
priority_queue<int> q;          //  大根堆  1 2 3

堆优化版 Dijkstra 算法适用于稀疏图，因此使用链式前向星进行建图

题目描述：

  • 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
  • 请你求出 1 1 1 号点到 n n n 号点的最短距离，如果无法从 1 1 1 号点走到 n n n 号点，则输出 − 1 −1 −1。
  • 1 ≤ n , m ≤ 1.5 × 1 0 5 1≤n,m≤1.5×10^5 1≤n,m≤1.5×105，图中涉及边长均不小于 0 0 0，且不超过 10000 10000 10000。数据保证：如果最短路存在，则最短路的长度不超过 1 0 9 10^9 109。
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII;
int h[N], e[N], w[N], ne[N], idx; // 链式前向星
int n, m, dist[N];
bool st[N];

void add(int x, int y, int z){
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}

void Dijkstra(){
	priority_queue<PII, vector<PII>, greater<PII>> q;
	q.push({0, 1}); // 先把起始位置存放进去，first存放的是距离（因为要根据距离排序）、second存放的是顶点编号
	while(q.size()){
		auto t = q.top();
		q.pop();
		int ver = t.second;
		if(st[ver]) continue;
		st[ver] = true;
		int dis = t.first;
		
		// 遍历从这个顶点出发的所有的边
		for (int i = h[ver]; ~i; i = ne[i]){
			int d = e[i];
			// 如果找到更短距离的则放进去
			if(dist[d] > (dis + w[i])){
				dist[d] = dis + w[i];
				q.push({dist[d], d});
			}
		}
	}
}

int main(){
	memset(h, -1, sizeof h);
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m;
	while(m--){
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
	}
	dist[1] = 0;
	Dijkstra();
	cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]);
	return 0;
}

Dijkstra（迪杰斯特拉）算法 只适用于边权为正值的情况下。为什么呢？

  • Dijkstra 算法当中将节点分为已求得最短路径的集合（记为S）和未确定最短路径的个集合（记为U），归入S集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与S内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度，而此时a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果。
  • 求带负权值边的单源最短路径可以用贝尔曼-福特算法。

bellman-ford算法

什么是贝尔曼-福特算法呢？

  • 贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman）和莱斯特·福特创立的，求解单源最短路径问题的一种算法。其优于 Dijkstra 的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但它也有特别的用处，一般用于实现通过m次迭代求出从起点到终点不超过m条边构成的最短路径。
  • Dijkstra算法不能解决带有负权边的问题，而Bellman-ford算法可以解决带有负权边的问题，是求解带负权边的单源最短路问题的经典算法。时间复杂度是 O ( n m ) O(nm) O(nm)，核心思想是”松弛操作”。解决带负权边的单源最短路问题还有一个常用的算法是SPFA算法，SPFA算法的时间复杂度一般是 O ( m ) O(m) O(m)，最坏是 O ( n m ) O(nm) O(nm)。
  • 总结：Dijkstra算法 可以解决不带负权边的问题，而对于带有负权边的问题，又有 Bellman-ford算法 和 SPFA 解决。

算法步骤：

  • 首先 n n n 次迭代，每一次循环所有边。我们这里用 a , b , w a,b,w a,b,w表示存在一条从 a a a 走到 b b b 的边，权重是 w w w。
  • 遍历所有边的时候更新一下其他点的距离，和 Dijkstra算法类似，用当前这个点更新和它相连的点距离起点的距离。
  • 用 d i s t dist dist 数组表示每个点到起点的距离，那么更新操作就是 d i s t [ b ] = m i n ( d i s t [ b ] , d i s t [ a ] + w ) dist[b]=min(dist[b],dist[a]+w) dist[b]=min(dist[b],dist[a]+w)，这样就可以更新和 a a a 相连的 b b b 点距离起点的距离，这个更新的过程就是”松弛操作”
for n次
	for 所有边 a,b,w (松弛操作)
		dist[b] = min(dist[b],back[a] + w)

注意：back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点

看个例子：

img

我们看这个图，红色的数字表示边的权重，我们想求一下 1 1 1 号点到 5 5 5 号点的最短路径，我们从 1 1 1 走到 2 2 2， 2 , 3 , 4 2,3,4 2,3,4 号点围成了一个圈，圈的总权重是 5 + − 4 + − 2 = − 1 5+-4+-2=-1 5+−4+−2=−1，那么转一圈长度就会减一，因此我们可以转无穷多圈，转无穷多圈总长度就会变成负无穷，出圈的话还是负无穷。所以说图中存在负权回路的话，从 1 1 1 号点到 n n n 号点的距离就会变成负无穷，就不存在了。

所以能求出来最短路的话，图中是没有负权回路的。

而 Bellman-ford算法 是可以判断图中存不存在负权回路。**首先上面的迭代次数是有实际意义的，比如我们迭代了 k k k 次，那么我们求的最短距离就是从 1 1 1 号点经过不超过 k k k 条边走到 n n n 号点的最短距离。**所以在第 n n n 次迭代的时候又更新了某些边的话，就说明路径中一定存在环，并且是负权回路。因为第 n n n 次迭代在不存在负权回路的情况下是遍历到第 n n n 号点了，后面是没有点了，如果还能更新，说明路径中存在回路，而且是负权回路。

但是一般找负环是不用 Bellman-ford算法，一般是用 SPFA算法，这里我们只要知道 Bellman-ford算法 可以找负权回路即可。

题目描述：

  • 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
  • 请你求出从 1 1 1 号点到 n n n 号点的最多经过 k k k 条边的最短距离，如果无法从 1 1 1 号点走到 n n n 号点，输出 impossible。
  • 注意：图中可能 存在负权回路 。
  • 1 ≤ n , k ≤ 500 1≤n,k≤500 1≤n,k≤500， 1 ≤ m ≤ 10000 1≤m≤10000 1≤m≤10000， 1 ≤ x , y ≤ n 1≤x,y≤n 1≤x,y≤n，任意边长的绝对值不超过 10000 10000 10000。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 505, M = 10010;
int n, m, k, dist[N], back[N];
struct edge{
	int x, y, z;
}edges[M];

void Bellman_ford(){
	for (int i = 0; i < k; i++){
		memcpy(back, dist, sizeof dist);
		for (int j = 1; j <= m; j++){
			auto e = edges[j];
			dist[e.y] = min(dist[e.y], back[e.x] + e.z);
		}
	}
}

int main(){
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++){
		cin >> edges[i].x >> edges[i].y >> edges[i].z;
	}
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	Bellman_ford();
	if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
	else cout << dist[n] << endl;
	return 0;
}

思考为什么要判断 dist[n] > 0x3f3f3f3f / 2 而不是直接判断 dist[n] == 0x3f3f3f3f 呢？这是因为如果存在负环，那么 dist 加上一个负数就会比 0x3f3f3f3f 小，但是它最终肯定不会到达终点，所以不能直接判断它是否等于 0x3f3f3f3f。

spfa算法

spfa算法 不仅可以用来求带负权边的最短路径问题，还可以用来判断是否存在负权回路。

其实 spfa算法 就是对 Bellman-Ford算法 的优化，就相当于 Dijkstra堆优化 版本是对 Dijkstra算法 的优化。在 Bellman_ford算法 会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点，这就是 spfa算法。

我们只需要添加一个 st 数组来维护当前结点是否在队列中（注意这里不是未使用过，而是不在队列中就可以加进去，可能一个顶点可以多次入队）

题目描述：

  • 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
  • 请你求出 1 1 1 号点到 n n n 号点的最短距离，如果无法从 1 1 1 号点走到 n n n 号点，则输出 impossible。
  • 数据保证不存在负权回路。
  • 1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105，图中涉及边长绝对值均不超过 10000 10000 10000。
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e6;
int h[N], e[N], w[N], ne[N], idx;
int n, m, dist[N];
bool st[N];

void add(int x, int y, int z){
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}

void spfa(){
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	st[1] = true;
	while(q.size()){
		int t = q.front();
		q.pop();
		st[t] = false; // 出队列之后变为false
		for (int i = h[t]; ~i; i = ne[i]){
			int j = e[i];
			if(dist[j] > dist[t] + w[i]){
				dist[j] = dist[t] + w[i];
				if(!st[j]){
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
}

int main(){
	memset(h, -1, sizeof h);
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m;
	while(m--){
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
	}
	spfa();
	if(dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
	else cout << dist[n] << endl;
	return 0;
}

Floyd算法

Floyd算法 可以说是最简单的一种最短路径算法，它就通过三层 for 循环简单实现。

它的思路是：对于从结点 i 到结点 j 的最短距离问题，看能否找到一个中间结点 k，使得从结点 i 到结点 k 的距离加上从结点 k 到结点 j 的距离小于直接从结点 i 到结点 j，相当于去找一个第三者。

同时，使用 Floyd算法 可以求得整个图中任意两点的距离。

题目描述：

  • 给定一个 n n n 个点 m m m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
  • 再给定 k k k 个询问，每个询问包含两个整数 x x x 和 y y y，表示查询从点 x x x 到点 y y y 的最短距离，如果路径不存在，则输出 impossible。
  • 数据保证图中不存在负权回路。
  • 1 ≤ n ≤ 200 1≤n≤200 1≤n≤200， 1 ≤ k ≤ n 2 1≤k≤n^2 1≤k≤n2， 1 ≤ m ≤ 20000 1≤m≤20000 1≤m≤20000，图中涉及边长绝对值均不超过 10000 10000 10000。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 205;
int n, m, k, dist[N][N];

void Floyd(){
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main(){
	memset(dist, 0x3f, sizeof dist);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) dist[i][i] = 0;
	while(m--){
		int x, y, z;
		cin >> x >> y >> z;
		dist[x][y] = min(dist[x][y], z);
	}
	Floyd();
	while(k--){
		int x, y;
		cin >> x >> y;
		if(dist[x][y] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
		else cout << dist[x][y] << endl;
	}
	return 0;
}

总结

37ff39642fd8f74476ddcd99944d1b4.png

  1. Dijkstra-朴素 O ( n 2 ) O(n^2) O(n2)
    • 初始化距离数组, dist[1] = 0, dist[i] = inf;
    • for n次循环 每次循环确定一个 min 加入 S 集合中，n 次之后就得出所有的最短距离
    • 将不在 S 中 dist_min 的点 ->t
    • t->S 加入最短路集合
    • 用 t 更新到其他点的距离
  2. Dijkstra-堆优化 O ( m l o g m ) O(mlogm) O(mlogm)
    • 利用邻接表，优先队列
    • 在 priority_queue[HTML_REMOVED], greater[HTML_REMOVED] > heap; 中将返回堆顶
    • 利用堆顶来更新其他点，并加入堆中类似宽搜
  3. Bellman_ford O ( n m ) O(nm) O(nm)
    • 注意连锁想象需要备份, struct Edge{inta,b,c} Edge[M];
    • 初始化 dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
    • 松弛 k 次，每次访问 m 条边
  4. Spfa O ( n ) 到 O ( n m ) O(n) 到 O(nm) O(n)到O(nm)
    • 利用队列优化仅加入修改过的地方
    • for k 次
    • for 所有边利用宽搜模型去优化 bellman_ford 算法
    • 更新队列中当前点的所有出边
  5. Floyd O ( n 3 ) O(n^3) O(n3)
    • 初始化 d
    • k, i, j 去更新 d

http://www.kler.cn/a/428601.html

相关文章：

  • 前端（三）html标签(2)
  • 数据中心可视化提升运维新高度
  • 多项式拟合之Math.NET Numerics
  • [Maven]下载安装、使用与简介
  • 【框架】环境切换集成封装
  • CSS3 布局样式及其应用
  • 【机器学习】机器学习的基本分类-监督学习-岭回归（Ridge Regression）
  • 4.1模块化技术之函数，本地类
  • Flink 核心知识总结：窗口操作、TopN 案例及架构体系详解
  • 如何使用 Python 实现链表的反转？
  • C++_关于异常处理throw-try-catch
  • MATLAB 非重叠点云提取算法（92）
  • C++的一些经典算法
  • java 服务端tcp方式接收和推送数据到c++或者qt（亲测可用）
  • 机器学习经典算法
  • C# 的GDI风车控件
  • FFmpeg+Nginx+VLC打造M3U8M3U8点播
  • STM32MX 配置CANFD收发通讯
  • Java 并发舞台：多线程小精灵的奇幻冒险之旅
  • 第二十二天 TensorFlow基础