【OI之路】03图论算法-1最短路之单源最短路(SPFA)

3.1.1定义

松弛:常听人说松弛,一直不懂,后来明白其实就是更新某点到源点最短距离。
邻接表:表示与一个点联通的所有路。
负权回路:从一个点沿着某条路径出发,又回到了自己,而且所经过的边上的权和小于0,该回路将导致算法不停循环以更小。
零环:边权都是0,理论上最短路将有无数种方案。

回归正题,SPFA是bellman-ford的一种改进算法,由1994年西安交通大学段凡丁提出。它无法处理带有负环的图(其实应该没有能处理负环的算法),判断方法:如果某个点进入队列的次数超过N次则存在负环。
SPFA的两种写法,bfs和dfs,bfs判别负环不稳定,相当于限深度搜索,但是设置得好的话还是没问题的,dfs的话判断负环很快(看不懂,喜欢宽搜)。

3.1.2 DFS版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n; //表示n个点,从1到n标号
int s,t; //s为源点,t为终点
int d[N]; //d[i]表示源点s到点i的最短路
bool vis[N];//vis[i]=1表示点i在队列中
int spfa_dfs(int x)
{
v[x]=true;
for(int k=hou[x];k!=0;k=e[k].next)
{
int y=e[k].y,c=e[k].c;
if(d[y]>d[x]+c)
{
d[y]=d[x]+c;
if(v[y] or spfa_dfs(y)) return true;
}
}
v[x]=false;
}

3.1.3 BFS版

结合题目来看看:

【题目描述】
给出一个有N个节点,M条边的带权有向图.判断这个有向图中是否存在负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路,求出一个点S到每个点的最短路的长度.
约定:S到S的距离为0,如果S与这个点不连通,则输出NoPath.
点数N,边数M,源点S;以下M行,每行三个整数a,b,c表示点a,b之间连有一条边,权值为c
如果存在负权环,只输出一行-1,否则按以下格式输出共N行,第i行描述S点到点i的最短路:
如果S与i不连通,输出NoPath;如果i=S,输出0;其他情况输出S到i的最短路的长度
【样例输入】
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4
【样例输出】
0 6 4 -3 -2 7

3.1.4 代码

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
75
76
77
78
79
80
81
82
83
84
85
struct point
{
int ans; //距离源点的最短距离
int hou; //最后的儿子
int p; //被放进序列(list)的次数统计
int v; //是否在序列(list)中
}a[99999];
struct road
{
int x,y,c,g;//起点、终点、长度和哥哥
}b[99999];
void BuildRoad(void);
void ShortRoad(int);
int list[99999],n,m,s,k;//路的数量
bool bo;
int main()
{
scanf("%d %d %d",&n,&m,&s);
k=0;
for(int i=1;i<=n;i++) a[i].hou=0;//放在建路之前
for(int i=1;i<=m;i++) BuildRoad();
bo=true;
for(int i=1;i<=n;i++)
{
ShortRoad(i);//寻找负权回路
if(bo==false)
{
printf("-1");
return 0;
}
}
ShortRoad(s);
for(int i=1;i<=n;i++)
if(a[i].ans==99999999) printf("NoPath\n");
else printf("%d\n",a[i].ans);
}
void BuildRoad(void)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
k++;
b[k].x=x;
b[k].y=y;
b[k].c=c;
b[k].g=a[x].hou;
a[x].hou=k;
}
void ShortRoad(int st)
{
for(int i=1;i<=n;i++)
{
a[i].ans=99999999;
a[i].p=0;a[i].v=0;
}
a[st].ans=0;a[st].p=1;
a[st].v=true;list[1]=st;
//放入序列中
int tou=1,wei=2;
if(wei>n) wei=1;//循环数组
while(tou!=wei)
{
int x=list[tou];
for(int i=a[x].hou;i>0;i=b[i].g)
{
int y=b[i].y;
if(a[y].ans>a[x].ans+b[i].c)
{
a[y].ans=a[x].ans+b[i].c;//松弛
if(a[y].v==false)//如果还没有放入
{
a[y].p++;
if(a[y].p>n)
{
bo=false;
return;
}
a[y].v=0;list[wei++]=y;
if(wei==n+1) wei=1;
}
}
}
a[x].v=false;tou++;
if(tou==n+1) tou=1;
}
}

3.1.5 一些补充

以下内容更新于2018.8.29
spfa的时间复杂度为 $O(km)$
在稀疏图上,k很小,但在稠密图上,有可能被卡成 $O(nm)$

介绍两个优化策略,通常来说能稍微提高效率
SLF(Small Label First)优化(本机房俗称酸辣粉优化):
基于双端队列(deque)的思想,更新完disy后,如果它比队头小,就放在前面,否则放在后面
然后如果没有负权边,可以用个堆取最小值,即堆优化spfa,但这个是没有任何意义的,
spfa的唯一一点点优势就是负权边,现在这样搞,那不如写dijkstra堆优化(其实单纯写法上只是标记是否清空而已)

LLL(Large Label Last)优化(本机房俗称啦啦啦优化):
维护队列的平均值,如果队首比平均值小,就丢到后面去

总的来说,这两个优化策略的基本思路就是不用堆,
保持能处理负权边的特性,但是又能尽量取出小的节点去拓展

最后,对于判断负权回路,还有第二种方式:
记录每个节点当前最短路径的边数,超过cnt则跳出,通常会更快一些

3.1.6 练习

智捅马蜂窝(变化不大)

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/8720.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%