图论最短路

学习
字数统计: 3.9k   |   阅读时长≈ 17 分钟

图论最短路

1. 单源最短路

从一个点到其他所有点的最短距离

  • 对于单源最短路径问题的时间复杂度和空间复杂度如下，对于空间复杂度需强调：对于稀疏图（边较少），倾向于使用邻接表和链式前向星，如果使用邻接矩阵容易爆内存；对于稠密图（边多），倾向于使用邻接矩阵，因为邻接表每个元素都是一个结点，占用的内存可能比邻接矩阵中的一格大，使用邻接矩阵反而内存占用更少。
  • 注意，无向图是一种特殊的有向图，所以我们背板子的时候不用特别区分有向图和无向图。
  • 对于稠密图（边的数量接近于顶点数量的平方），使用邻接矩阵的时间复杂度通常更低，因为你可以在 $O(1)$ 的时间内访问任何边。然而，邻接矩阵的空间复杂度是 $O(V^2)$ ，这可能会导致内存超限。
  • 对于稀疏图（边的数量远小于顶点数量的平方），使用邻接表的时间复杂度通常更低，因为你只需要遍历与每个顶点相连的边。邻接表的空间复杂度是 $O(E)$ ，这通常比邻接矩阵更节省空间。
image-20231018161346568

1.1. 所有边权都是正数

1.1.1. 朴素 $Dijkstra$ 算法

时间复杂度 $O(n²)$：$n$ 表示点的数量，和边数无关，适合稠密图，空间复杂度 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 朴素dijkstra
// 1:初始化距离,dist[1]=0,dist[v]=+inf,s是当前已经确定最短距离的点
// 2:for v in [1,n]:①不在s中的距离最近的点;②t→s;③用t更新其他点的距离
// 3:循环n次后,已经求出每个点到第一个点的最短距离

// 稠密图→邻接矩阵
const int N=5e2+5; 
// 点最大是500*500=2.5*10^5>题目给的m最大值
// 注意:存在重边和自环
int n,m;
int g[N][N]; // 存储图
int dist[N]; // 每个点到第一个点的距离
bool st[N]; // 每个点的访问状态

int dijkstra() {
	// 先把距离初始化为不可达
	memset(dist,0x3f,sizeof dist);
	dist[1]=0; // 第一个点到自身的距离为0
	// 对于每一个结点,我们每遍历一次就把一个点加入到已经找到最短路径的队列中
	for(int i=0;i<n;i++) {
		int t=-1; // 初始化t为-1,t用于记录当前未被访问的结点中距离源节点最近的结点
		// 遍历所有结点,找到每个结点距离自己最近且尚未加入"已经找到最短路径"点集的结点
		for(int j=1;j<=n;j++)
			// !st[j]:结点j未被访问,t为-1,或者t到源节点的距离小于j到源节点的距离
			if(!st[j] && (t==-1 || dist[t]>dist[j]))
				t=j;
		
		// 如果当前结点的最近结点就是n,那么直接跳出(优化意义不明显)
		if(t==n)
			break;
		
		st[t]=true;
		// 以t为跳板,更新所有结点到源节点的最短距离
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],dist[t]+g[t][j]);
	}
	// 不存在最短路返回-1,存在则返回最大距离值
	if(dist[n]==0x3f3f3f3f)
		return -1;
	return dist[n];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	// 初始化邻接矩阵为互不可达
	memset(g,0x3f,sizeof g);
	while(m--) {
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c); // 去除重边
	}
	int t=dijkstra();
	cout<<t<<endl;
	return 0;
}

1.1.2. 堆优化 $Dijkstra$

时间复杂度 $O(mlogn)$：$n$ 表示点的数量、$m$ 表示边的数量，适合稀疏图，空间复杂度 $O(m+n)$

  • 该代码可以解决带有重边和自环的有向图、无向图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e6+5;
const int M=N;
int n,m;
// h:每个结点的第一条边
// e:每条边的下一个结点
// ne:每条边的下一条边
// w:每条边的权重
int h[N],e[N],ne[N],w[N],idx;
int dist[N]; // 邻接表存储最短距离
bool st[N]; // 访问状态

void add(int a,int b,int c) {
    // 第idx条边指向节点b,第idx边边权为c,第idx条的下一条边是a的起始边(头插法思想),起始边更新为当前边编号,编号自增
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra() {
	// 初始化互不可达
	memset(dist,0x3f,sizeof dist);
	// 编号为1的点到自己距离为0
	dist[1]=0;
	priority_queue<PII,vector<PII>,greater<PII>> heap; // 小根堆
	heap.push({0,1}); // 距离为0,点编号为1(第一关键字存储距离,小根堆默认从小到大排序;第二关键字存储编号)
	
	// 队列不为空
	while(heap.size()) {
		// 取出头结点
		auto t=heap.top();
		heap.pop();
		
		// v:取出头结点的编号
		// distance:到源节点的距离
		int v=t.second;
		// 如果已访问过,则跳过
		if(st[v])
			continue;
		st[v]=true;
		// 遍历该结点的所有边,-1是尾边(因为用的是头插法)
		for(int i=h[v];i!=-1;i=ne[i]) {
			int j=e[i];
			// 如果距离更短,则更新
			if(dist[j]>dist[v]+w[i]) {
				dist[j]=dist[v]+w[i];
				// 节点j的距离和编号加入队列
				heap.push({dist[j],j});
			}
		}
	}
	
	// 如果不可达,返回-1
	if(dist[n]==0x3f3f3f3f)
		return -1;
	return dist[n]; // 否则范围到节点n的距离
}

int main() {
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--) {
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
        // add(b,a,c); // 无向图
	}
	cout<<dijkstra()<<endl;
	return 0;
}

1.2. 存在负权边

  • $SPFA$ 一般比贝尔曼福特快，如果想求不超过 $k$ 条边的最短路，只能用贝尔曼福特算法来做。需要注意一点，如果存在负权回路，那么最短路是不一定存在的，贝尔曼福特算法可以求出是否存在负权回路，如果存在负权回路，贝尔曼福特可能求不出最短路径

  • 需要注意的是：$SPFA$ 的使用条件是，一定不存在负环，SPFA本质上是对Bellman-Ford的优化，也可以用于找负环

  • $80%$ 的正权图也能用 $SPFA$ 来做，且时间效率会比 $dijkstra$ 更快，但是如果 $SPFA$ 被卡了，$SPFA$ 的平均时间复杂度是$O(m)$，最坏的情况是$O(nm)$，数据给的差是可能达到最坏情况的，如果被卡了，就换成堆优化的 $dijkstra$

1.2.1. Bellman-Ford

时间复杂度 $O(nm)$，题目链接：853. 有边数限制的最短路 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// Bellman-Ford算法,注意该算法存边随便存,只要能遍历所有边即可
// for循环n次,每一次循环所有边a,b,w,更新最短距离(三角不等式)
// 迭代k次后,dist数组代表的含义:从1号点经过,不超过k条边走到每个点的最短距离
// 如果第n次迭代后dist数组有更新的话,说明一定存在负环,SPFA也可以找负环

// SPFA一般在任何情况都优于Bellman-fort
// 但是如果有边数限制,如AcWing853,最多经过不超过k条边的最短路径,必须用Bellman-fort

const int N=5e2+10;
const int M=1e5+10;

int n,m,k; // 点/边/最短路边限制
int dist[N],backup[N];

struct Edge {
	int a,b,w;	
}edges[M];

int bellman_ford() {
	// 初始化不可达
	memset(dist,0x3f,sizeof dist);
	dist[1]=0; // 结点1到自身距离为0
	
	// 走k步路
	for(int i=0;i<k;i++) {
        // 把dist写进backup
		// 每次复制上一次的状态,因为要求在k步路内的最短距离,所以不能直接更新
		memcpy(backup,dist,sizeof dist);
		for(int j=0;j<m;j++) {
			int a=edges[j].a,b=edges[j].b,w=edges[j].w;
			dist[b]=min(dist[b],backup[a]+w);
		}
	}
	// 为什么这里不是0x3f3f3f3f呢?
	// 因为如果两个点对于点1都是不可达,但相互可达,则可能在更新时变成不是0x3f3f3f3f的数
	// 所以这里用一个类似于极大值的数来替代
	// 如果没有最短路径,返回0x3f3f3f3f,不返回-1是因为有可能最短距离就是-1
	if(dist[n]>0x3f3f3f3f/2)
		return 0x3f3f3f3f;
	return dist[n];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=0;i<m;i++) {
		int a,b,w;
		cin>>a>>b>>w;
		edges[i]={a,b,w};
	}
	int t=bellman_ford();
	if(t==0x3f3f3f3f)
		cout<<"impossible";
	else
		cout<<t<<endl;
	return 0;
}

1.2.2. SPFA

时间复杂度 一般 $O(m)$，最坏 $O(nm)$，以下模板无视重边和自环，题目链接：851. spfa求最短路 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// SPFA:长得特别像dijkstra,对于负权图,如果出题人卡SPFA的话就没办法了
// 只要队列不为空
// 弹出队头t,更新t的所有出边
const int N=1e5+5;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c) {
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa() {
	// 初始化dist为不可达
	memset(dist,0x3f,sizeof dist);
	// 第一个点的距离为0
	dist[1]=0;
	queue<int> q;
	q.push(1);
	st[1]=true;
	while(q.size()) {
		// 弹出队头
		int t=q.front();
		q.pop();
		// 更新状态
		st[t]=false;
		// 遍历每条边
		for(int i=h[t];i!=-1;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;
				}
			}
		}
	}
	// 不可达不要返回-1,因为有可能最短路径就是-1
	if(dist[n]==0x3f3f3f3f3)
		return 0x3f3f3f3f;
	return dist[n];
}

int main() {
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--) {
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	int t=spfa();
	if(t==0x3f3f3f3f)
		cout<<"impossible";
	else
		cout<<t<<endl;
	return 0;
}

1.2.3. SPFA判负环

题目链接：852. spfa判断负环 - AcWing题库

  • 维护一个 $cnt$ 数组，从 $[1,x]$，$cnt$ 数组记录的是在用 $SPFA$ 找$1$号点 到 $n$号点最短路径时，这个最短路中边的个数，如果 $dist[j]>dist[v]+w[i]$ 说明我从 $v$ 这个点到 $j$ 的距离更短，那么从 $i$ → $j$ 就更新为 $i$ → $v$ → $j$，所以边数要 $+1$ ，即有 $cnt[j]=cnt[v]+1$ ，如果在某一次中 $cnt[x]>=n$ 了，说明一共经历了 $n$ 条边，有$n$ 条边就有 $n+1$ 个点，但是题目中只有 $n$ 个点，说明有一个点出现了两次，即出现了环，又因为 $dist$ 是在不断减小的，所以这一定是一个负环
  • 还需要注意一点，一开始我们不能直接把 $1$ 号点放进队列来找，因为题目要找的是整个图中是否存在负环，而从 $1$ 号点出发不一定能到这个负环，所以做法是把所有点都放进队列中，那么一定能找到这个负环
  • 注意 $SPFA$ 判负环时间复杂度其实还蛮高的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e5+10;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
bool st[N];
int cnt[N]; // 判断有无负环,cnt[i]:表示遍历到第i个节点时已遍历过的节点总数

void add(int a,int b,int c) {
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa() {
	queue<int> q;
	// 注意这里不能把1放进去,因为1可能到不了这个负环
	
//	q.push(1);
    // 把每个点都放进去判断
	for(int i=1;i<=n;i++) {
		st[i]=true;
		q.push(i);
	}
	
	while(q.size()) {
		int t=q.front();
		q.pop();
		
		st[t]=false;
		
		for(int i=h[t];i!=-1;i=ne[i]) {
			int j=e[i];
			if(dist[j]>dist[t]+w[i]) {
				dist[j]=dist[t]+w[i];
				cnt[j]=cnt[t]+1; // 遍历到节点j时遇到的节点总数+1
				if(cnt[j]>=n) 
					return true; // 有负环
				if(!st[j]) {
					q.push(j);
					st[j]=true;
				}
			}
		}
	}
	return false;
}

int main() {
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--) {
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	if(spfa()) {
		cout<<"Yes";	
	} else {
		cout<<"No";
	}
	return 0;
}

2. 多源汇最短路

求多个起点到其他点的距离

2.1. Floyd算法

时间复杂度O(n³)，dp的外表，暴力的心，题目链接：854. Floyd求最短路 - AcWing题库，以下模板能处理重边、自环、负权边，但不能处理负权回路，因为存在负权回路时距离会不断往下越来越小，无法收敛

  • 注意之所以用 $d[a][b]>INF/2$ 来判断是否是不可达是因为题目中存在负权边更新后的距离很有可能比 $INF$ 小一些，要在其他负权边存在的最短路问题中也注意一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 弗洛伊德:多源最短路,直接暴力暴暴暴就完事了
// 第一层循环,k从1~n,枚举i→j的中间节点
// 第二层循环,i从1~n
// 第三层循环,j从1~n
// d[i,j]=min(d[i][j],d[i][k]+d[k][j])
// 原理:d[k,i,j]=d[k-1,i,k]+d[k-1,k,j],基于dp

const int N=2e2+2;
const int INF=1e9;

int n,m,Q; // Q是循环次数
int d[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++) {
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}

int main() {
	cin>>n>>m>>Q; 
	// 重边和自环的处理方法:
	// 重边:保留最小的边
	// 自环:删除
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(i==j)
				d[i][j]=0; // 自己到自己的距离为0,赋初值,后比较,去自环
			else
				d[i][j]=INF; // 初始化邻接矩阵为互不可达
		}
	}
	
	while(m--) {
		int a,b,c;
		cin>>a>>b>>c;
		d[a][b]=min(d[a][b],c); // 去重边,保留最小边(邻接矩阵的做法)
	}
	floyd();
	while(Q--) {
		int a,b;
		cin>>a>>b;
		
		if(d[a][b]>INF/2) // 可能会被更新得不是INF
			cout<<"impossible"<<endl;
		else
			cout<<d[a][b]<<endl;
	}
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信