一、求正权图的单源最短路
对于求正权图的单源最短路问题,我们一般使用Dijistra算法求解
Dijistra算法
Dijistra算法的基本思想是贪心。
我们可以先把所有点的距离设为一个无穷大的数,然后将起始点的dis设为一,每次找一个dis最小并且没有被标记过的点,然后将这个点打上标记,查询这个边所有的出边,设原点为i,这条出边对应的点为j,这条边的边权为v,则当disi+v<disj时更新disj的值,当所有边都被标记时,从这个点到其它点的最短路就都求出来了。
代码实现
时间复杂度O(n2)
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
| #include<iostream> #include<algorithm> #include<cmath> #include<array> #include<bitset> using namespace std; using gg=long long; array<gg,200010> nxt,to,val; array<gg,100010> head,dis; bitset<100010> fl; gg cnt=0; void add(const gg &x,const gg &y,const gg &v) //链式前向星存图 { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=v; return; } int main() { gg n,m,x,y,v; //n个点,m条边 cin>>n>>m; while(m--) //建图 { cin>>x>>y>>v; add(x,y,v); } for(gg i=1;i<=n+1;i++) dis[i]=114514114514; dis[1]=0; while(1) { gg x=n+1; for(gg i=1;i<=n;i++) { if(dis[x]>dis[i]&&fl[i]==false) { x=i; } } if(x==n+1) break; fl[x]=true; for(gg i=head[x];i;i=nxt[i]) { if(dis[x]+val[i]<dis[to[i]]) { dis[to[i]]=dis[x]+val[i]; } } } for(gg i=1;i<=n;i++) { cout<<dis[i]<<'\n'; } return 0; }
|
这时候,细心的同学可能已经发现了嗷——这个找dis最小值的操作完全可以使用STL中的优先队列实现
改进后代码
时间复杂度O(nlogn)
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
| #include<iostream> #include<array> #include<algorithm> #include<cmath> #include<vector> #include<bitset> #include<queue> #include<utility> using namespace std; using gg=long long; array<gg,400010> nxt,to,val; array<gg,200010> head,dis; bitset<200010> fl; priority_queue<pair<gg,gg>,vector<pair<gg,gg>>,greater<pair<gg,gg>>> list; gg cnt=0; void add(const gg &fr,const gg &t,const gg &v) { cnt++; to[cnt]=t; nxt[cnt]=head[fr]; head[fr]=cnt; val[cnt]=v; return; } int main() { gg n,m,x,z,y,s; cin>>n>>m>>s; for(gg i=1;i<=m;i++) { cin>>x>>y>>z; add(x,y,z); } for(gg i=1;i<=n;i++) { dis[i]=114514114514; } dis[s]=0; list.push(make_pair(0,s)); while(!list.empty()) { gg poi=list.top().second; list.pop(); if(fl[poi]) continue; fl[poi]=true; for(gg i=head[poi];i;i=nxt[i]) { if(dis[poi]+val[i]<dis[to[i]]) { dis[to[i]]=dis[poi]+val[i]; list.push(make_pair(dis[to[i]],to[i])); } } } for(gg i=1;i<=n;i++) { cout<<dis[i]<<' '; } cout<<'\n'; return 0; }
|
Dijistra练习题
洛谷P4779 【模板】单源最短路径(标准版)
二、求带负边的单源最短路
如果图中存在负边,Dijistra算法就不能用了,因为其中的判断会不断加上这条负边从而出现更小的数,这个时候,就是著名的SPFA算法出场的时候了!
SPFA算法
SPFA算法维护一个队列,首先把起点处的dis更新为0,其余初始化为无穷大,并将起点加入队列中,打上标记。每次取出队头的一个点,并把这个点的标记消除,扫描这个点的所有出边,设原点为i,这条出边对应的点为j,这条边的边权为v,则当disi+v<disj时更新disj的值并查看点j是否在队列中,如果不在就将点j加入队列,并打上标记。当队列为空时,就求出了原点到各个点的最短路。
注意:SPFA在应对随机数据时为O(kn)的时间复杂度,其中k是一个较小的数,但当数据为特殊构造时,此算法的时间复杂度会被卡到O(nm),因此使用此算法时应三思而后行
代码实现
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
| #include<iostream> #include<algorithm> #include<cmath> #include<array> #include<queue> #include<bitset> using namespace std; using gg=long long; array<gg,200010> nxt,to,val; array<gg,100010> head,dis; bitset<100010> fl; queue<gg> list; gg cnt=0; void add(const gg &x,const gg &y,const gg &v) //链式前向星存图 { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; val[cnt]=v; return; } int main() { gg n,m,x,y,v; //n个点,m条边 cin>>n>>m; while(m--) //建图 { cin>>x>>y>>v; add(x,y,v); } for(gg i=1;i<=n+1;i++) dis[i]=114514114514; //初始化 dis[1]=0; list.push(1); fl[1]=true; while(!list.empty()) //SPFA { gg p=list.front(); list.pop(); fl[p]=false; for(gg i=head[p];i;i=nxt[i]) { if(dis[p]+val[i]<dis[to[i]]) { dis[to[i]]=dis[p]+val[i]; if(!fl[to[i]]) list.push(to[i]),fl[to[i]]=true; } } } for(gg i=1;i<=n;i++) { cout<<dis[i]<<'\n'; } return 0; }
|
感谢阅读!