最短路习题技巧

最短路习题技巧

九月 01, 2021

这次我们来看一下图论的一些有趣的操作与性质

spfa判断负环

首先我们把spfa的代码放过来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	dis[1]=0; vis[1]=true;
	Q.push(1);
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		vis[x]=false;
		for(int i=head[x];i;i=edge[i].next){
			int y=edge[i].to,z=edge[i].w;
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				if(!vis[y]){
					Q.push(y);
					vis[y]=true;
				}
			}
		}
	}
}

然后我们观察，一个数入队的条件是：前一个点当前的dis加上权值w<当前扫描到的边的dis

那么如果出现正环，那么他们每一轮都不会相加，因为显然每加一轮会加上这个环的大小，所以正环不会出现死循环

但是如果出现负环，每一轮过后最短路都会变小，那么我们就可以用spfa来判断负环

方法：计算一下入队的数的个数如果大于等于n，就说明有负环，可以直接跳出了（此处用的是bfs的思路）

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
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	dis[1]=0; vis[1]=true;
	Q.push(1);
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		vis[x]=false;
		for(int i=head[x];i;i=edge[i].next){
			int y=edge[i].to,z=edge[i].w;
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;
				cnt[y]=cnt[x]+1;  //更新包含边数
				if(cnt[y]>=n) return true;  //判定存在负环
				if(!vis[y]){
					Q.push(y);
					vis[y]=true;
				}
			}
		}
	}
	return false;
}
//上面的更新包含边数可以再说一下，就是说，每当一个环出现，那么肯定要循环跑一串点，所以我们可以记录下每一个点进入多少次，如果一个点进入了n次及以上，就说明有负环了，可以直接跳出

建反边

我们先看一个题：对于一个有向图，从节点1出发，共n个点，每到一个节点立即返回，问最短的总路径是多少
易知我们从节点1到每个点可以用dijkstra跑一遍，那么怎么跑回来呢？每次循环再走一遍？那复杂度不堪设想
所以我们想到可以把边反过来建，这样我们算各个点到节点1的距离可以反过来，重新在建反边的前提下跑一遍dijkstra(1)，这就是建反边的思想