[单源最短路]两大优化算法争锋之SPFA与堆优化版Dijkstra

单源最短路(SSSP)的算法有Dijkstra,Bellman-Ford, 两大算法优化后即为Dijkstra+heap与SPFA。

这两个优化版算法写起来非常相似。接下来就从算法思路、时间复杂度、写法和适用场景上进行对比分析。

基础算法

Dijkstra

时间复杂度:O(V2+E)

n-1次循环

–>找到未标记的d最小的点

–>标记,松弛它的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dijkstra(int s){
memset(vis, false, sizeof(vis));
vis[s] = true;
for(int i = 1; i <= n; i++)
dis[i] = road[s][i];
for(int u = 1; u<n; u++){
int minD = inf,k = -1;
for(int i = 1; i<= n; i++){
if(!vis[i]&&dis[i]<minD){
k = i;
minD = dis[i];
}
}
vis[k] = true;
for(int i = 1; i<= n; i++){
if(!vis[i]&&dis[k]+road[k][i]<dis[i]){
dis[i]=dis[k]+road[k][i];
}
}
}
}

Bellman-Ford

时间复杂度:O(VE)

n-1次循环

–>对所有边松弛

还能再松弛则有负环

1
2
3
4
5
6
7
8
9
10
int dis[10010];
int u[10010],v[10010],w[10010];
int n,m;
void Bellman_ford(int a){
memset(dis,inf,sizeof(dis));//赋初始值
dis[a]=0;
for(int i=1;i<=n-1;i++)//更新n-1次
for(int j=1;j<=m;j++)//更新每一条边
dis[v[j]]=min(dis[v[j]],dis[u[j]]+w[j]);//判断是否更新
}

两大基础算法对比

  • Dijkstra是每次确定了到一个点的最短距离,再用该点更新到其它点的距离。不能处理有负边的图。
  • Bellman-Ford是每次对所有边松弛。可以计算出有负边无负环的最短路,可以判断是否存在负环。

优化算法

Dijkstra+heap优化

时间复杂度:O((V+E)lgV)

用STL中的优先队列实现堆:

while(优先队列非空)

–>队头出队,松弛它的边

–>松弛了的<新距离,点>入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
...
while(!q.empty()){ // O(V) 加上count<n可以优化一点点
int w=q.top().first, u=q.top().second;
q.pop(); // O(lgV)
if(b[u])continue; b[u]=true;
//++count;
for(int i=head[u];i;i=e[i].next){ // Sum -> O(E)
int v=e[i].to;
if(d[u]+e[i].w<d[v]){
d[v]=d[u]+e[i].w;
q.push(PII(d[v],v)); // O(lgV)
}
}
}

SPFA

时间复杂度:O(kE) or O(VE)

while(队非空)

–>队头出队,松弛它的边

–>松弛了且不在队内的点入队

1
2
3
4
5
6
7
8
9
10
11
while(!q.empty()){
int u=q.front(); q.pop();
b[u]=false;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(d[u]+e[i].w<d[v]){
d[v]=d[u]+e[i].w;
if(!b[v])b[v]=true,q.push(v);
}
}
}

算法思路对比

  • Dijkstra+heap是用小根堆,每次取出d最小的点,来更新距离,那么这个点来说,最小距离就是当前的d。
  • SPFA是用双端队列,每次取出队头,来更新距离,它之后可能还会入队。它是一种动态逼近法,因为每次松弛距离都会减小,所以松弛一定会有结束的。如果一个点入队超过n次就是存在负环。

复杂度分析对比

Dijkstra+heap

  • 因为是堆,取队头需要O(lgV)。
  • 松弛边时,因为点的d改变了,所以点v需要以新距离重新入堆,O(lgV),总共O(ElgV)。
  • 因此总的是O((V+E)lgV)

SPFA

  • 论文证明也不严格。复杂度不太好分析。
  • 总的是O(kE)。k大概为2
  • 复杂度应该是 O(VE)。

适用场景

如果是稠密图,Dijkstra+heap比SPFA快。稀疏图则SPFA更快。SPFA可以有SLF和LLL两种优化,SLF就是d比队头小就插入队头,否则插入队尾。

另外,Dijkstra和Prim也很相似,它们的区别主要是d的含义,前者是到s的临时最短距离,后者是到树的临时最短距离,相同点是,每次找d最小的更新其它点的距离。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxx = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5+7;
int t,n,m,cnt;
ll dis[maxn];
bool vis[maxn];
int head[maxn];
struct EDGE{
int next;
int to;
ll w;
}edge[2*maxn];
struct NODE{
int u;
ll dis;
NODE(){}
NODE(int u,ll w):u(u),dis(w){}
bool operator <(const NODE &a)const
{
return dis>a.dis;
}
}node[2*maxn];
void add(int u, int v, ll w){
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt;
cnt++;
}
void dijkstra(int s){
memset(dis,maxx,sizeof(dis));
memset(vis,false,sizeof(vis));
priority_queue<NODE>q;
q.push(NODE(s,0));
while(!q.empty()){
int kk = q.top().u;
ll minD = q.top().dis;
q.pop();
if(vis[kk])
continue;
vis[kk] = true;
for(int l = head[kk]; l!=-1; l=edge[l].next){
if(!vis[edge[l].to]&&minD + edge[l].w < dis[edge[l].to]){
dis[edge[l].to] = minD + edge[l].w;
q.push(NODE(edge[l].to,dis[edge[l].to][j]));
}
}
}
}
int main(){
ll u,v,w;
scanf("%d",&t);
while(t--){
memset(head,-1,sizeof(head));
cnt = 0;
scanf("%d%d",&n,&m);
for(int i = 0;i < m; i++){
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);
}
dijkstra(1);
if(dis[n]!=maxx)
printf("%lld\n",dis[n]);
else
printf("0\n");
}
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!