勇敢小鸡,不怕困难。时隔多日,又来复习图论算法了,本来想的是搞一下差分约束的,但是发现前置知识是spfa算法,所以就先来学习一下这个。

spfa算法介绍

SPFA算法是求解单源最短路径问题的一种算法,由理查德·贝尔曼(Richard Bellman) 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作,得到所有可能的最短路径。其优于dijkstra算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达 O(VE)。但算法可以进行若干种优化,提高了效率。

算法的思路:
我们用数组dis记录每个结点的最短路径估计值,用邻接表或邻接矩阵来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止

我们要知道带有负环的图是没有最短路径的,所以我们在执行算法的时候,要判断图是否带有负环,方法有两种:

  1. 开始算法前,调用拓扑排序进行判断(一般不采用,浪费时间)
  2. 如果某个点进入队列的次数超过N次则存在负环(N为图的顶点数)

spfa算法浅谈

spfa算法的话,一般单源最短路基本用不到 ,dijkstra算法比它优很多,唯有需要处理负权图的时候会想到他。差分约束无解的情况就是存在负环,因此这个得学。

大概流程可以描述为以下文字。

  1. 源点入队,源点距离初始化为0,其它初始化为 $inf$。
  2. 出队一个点并遍历与之之间相连的点,进行松弛操作。也就是我们经常见到的 if(dis[to]>w+dis[from])dis[to]=dis[from+w]
  3. 如果对一个点进行了松弛那么判断它有没有在队列中,如果不在则入队,并判断入队次数有没有超过点的个数,如果超过则goto 6。
  4. 如果队列不为空则goto 2。
  5. 结束,输出结果。
  6. 结束,输出存在负环的对应答案。

下面来一道例题。

洛谷P1396

题目描述

妈妈下班回家,街坊邻居说小明被一群陌生人强行押上了警车!妈妈丰富的经验告诉她小明被带到了 t 区,而自己在 s区。

该市有 m 条大道连接 n 个区,一条大道将两个区相连接,每个大道有一个拥挤度。小明的妈妈虽然很着急,但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线,使得经过道路的拥挤度最大值最小。

题目分析

这题其实有点差强人意,因为这个是要判断所经过边的最大值的最小值,但是我们主要还是练习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
#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
struct eee{
int to;
int next;
int w;
}edge[maxn<<2];
int root[maxn],cnt,dis[maxn],in_que[maxn];
int n,m,s,t;
void add(int x,int y,int w){
edge[++cnt].to=y;
edge[cnt].w=w;
edge[cnt].next=root[x];
root[x]=cnt;
}
void sync(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void spfa(){
memset(dis,0x3f,sizeof(dis));
queue<int>q;
q.push(s);
dis[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to,w=edge[i].w;
//printf("%d %d %d\n",u,v,w);
if(dis[v]>max(dis[u],w)){
dis[v]=max(dis[u],w);
if(!in_que[v]){
q.push(v);
in_que[v]=1;
}

}
}
in_que[u]=0;
}
}
int main(){
//freopen("P1396_1.in","r",stdin);
sync();
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
add(x,y,w);
add(y,x,w);
}
spfa();
printf("%d\n",dis[t]);
return 0;
}