最短路--SPFA

SPFA是个很神奇的算法,他在一般情况下时间会跑的很快,肯定有人想用SPFA来代替dijkstra,但是有一种特殊的数据专门来卡SPFA,只能让dijkstra过,SPFA过不去,那就是网格图,我稍后会讲为什么网格图可以卡掉SPFA。

但是为什么SPFA跑不过dijkstra,大家还要用SPFA?因为dijkstra只能计算不带负环的图,当图中出现负环,dijkstra就会一直卡在负环里出不来了。如果不太懂可以看一看我的上一篇博客:Dijkstra

当图中存在可到达的负环,则该图一定不存在最短路,因为负环可以一直当做最短路来松弛其他边,那么最短路就能无限小,所以不存在最短路。

img

SPFA也是用来求单源最短路,它当然也不能在存在可达负环的时候计算最短路,但是他有一个神奇的功能:判断图中是否存在可达负环

Bellman-Ford

SPFA是Bellman-Ford的队列优化,在一般情况下比Bellman-Ford快很多。这里介绍Bellman-Ford是希望可以更好地理解SPFA,因为两者本质区别不大。

算法步骤

算法总共跑n-1轮就能确定所有点的最短路。总共有n个点,x1, x2, x3, x4…xn,其中x1为源点,第一轮一定可以确定离源点最近的点的最短路,即x2的最短路。依次类推,如果图中不存在负环,则一定能在n-1轮推出所有点的最短路。

算法实现

下面把敦爷讲课的时候的代码放出来:

1
2
3
4
5
6
7
8
for(int k=1; k<=n-1; k++)
{
for(int i=1; i<m; i++)
{
if(dis[v[i]] > dis[u[i]]+w[i])
dis[v[i]] = dis[u[i]]+w[i]
}
}

SPFA

观察上面的Bellman-Ford可发现,当dis[u]没有被更新的时候,它依然会用dis[u]去松弛其它边,这样就做了很多冗余的操作,我们用一个队列来优化它,就是当有一个点被更新了,如果这个点没在队列里面,就把它放到队列里面去。这样一个点很久没有被更新过的话,就不会用它去更新其它边。

算法实现

此处建议先看懂我的上一篇博客:Dijkstra

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
int dis[maxn], viscnt[maxn];
bool inq[maxn];
vector<pair<int, int> > G[maxn];//1.

void add_eage(int s, int t, int w)
{
G[s].push_back(make_pair(w, t));//2.
G[t].push_back(make_pair(w, s));//3.
}
void init(int n)//4.
{
for(int i=0; i<n; i++)
G[i].clear();
}


bool SPFA(int n, int s)//5.
{
for(int i=0; i<n; i++)//6.
{
dis[i] = (i==s)?0:INF;
inq[i] = false;
viscnt[i] = 0;
}

queue<pair<int, int> > q;
q.push(make_pair(dis[s], s));//7.
inq[s] = true;
while(!q.empty())
{
pair<int, int> p = q.front();
int x = p.second;//8.
q.pop();
inq[x] = false;

if(viscnt[x]++>n)//9.
return true;

for(int i=0; i<G[x].size(); i++)//10.
{
int y=G[x][i].second, w=G[x][i].first;
if(dis[x]+w<dis[y])//11.
{
dis[y] = dis[x]+w;
if(!inq[y])
{
q.push(make_pair(dis[y], y));
inq[y] = true;
}
}
}
}
return false;
}

注释:

  1. viscnt[i]用来计数第i个点被更新了几次,如果更新次数超过n,则说明图中存在负环。inq[i]表示第i个点是否在队列里面。存放pair的vector用来存放边和边权,G[i] [j]存放的是和结点i相连的第j条边。G[i] [j].second存放的是和结点i相连的第j条边的另一个端点。G[i] [j].first存放的是和结点i相连的第j条边的权重。maxn为自己定义的常量。
  2. 将边添加至vector中,s、w、t 说明同上。
  3. 无向图的边是无向的,所以需要在G[s]和G[w]中都加入一条边。有向图不需要这一步。
  4. 初始化vector,清空所有先前加入的边。
  5. SPFA当图中存在负环时返回true不存在时返回false
  6. 初始化dis数组,将源点到源点的距离设置为0,其他的设置为INF(自己定义)。viscnt和inq设为0和false。
  7. 将源点压入队列。inq[s]设为true。
  8. 依次取队首元素。取出后inq[i]设为false。
  9. 每次访问一个点,令这个点的viscnt++,当这个点的访问次数超过n次,则说明图中存在负环。
  10. 依次遍历与x相连的边,y表示与x相连的边的另一端结点编号。w表示x到y路径权重。
  11. 进行松弛操作,如果某个点松弛操作成功,则把它压入队列。

如何卡SPFA

因为SPFA没回更新的时候用的是一条边去更新,被更新过的点入队。

比如说我们有一条链

img

当我们用边0-1去更新后面所有边之后,如果边0-1又被更新,则后面的所有边都要被依次再更新一遍。

这样SPFA的时间复杂度就会变得非常高

参考

  1. 夜深人静写算法(四)- 最短路和差分约束
  2. 2019ccpc夏令营敦爷讲的图论
Donate comment here