首页 > 代码库 > 最短路

最短路

2024-09-20 05:13:55   223人阅读

多源最短路

Floyd

时间复杂度:O(n3)；空间复杂度:O(n2)
1 for(int k=1;k<=n;k++)2 for(int i=1;i<=n;i++)3 for(int j=1;j<=m;j++)4 map[i][j]=min(map[i][j],map[i][k]+map[k][j];

 

单源最短路

SPFA

初始化最短路径表；

源点入队；

取出队首点；

枚举取出点的边；

如果能松弛，就松弛，并把被松弛的点加入队列；

如此循环直到队列为空。

 1 #include<cstdio> 2 int n,m,s,v[10010]; 3 int a,b,c; 4 int q[500010],head,tail; 5 int h[10010],hs; 6 struct edge{int s,n,v;}e[500010]; 7 inline bool rel(long long x,long long y,long long z){return y+z<x?1:0; } 8 int main(){ 9     scanf("%d%d%d",&n,&m,&s);10     for(int i=1;i<=n;i++) if(i!=s) v[i]=2147483647;11     for(int i=1;i<=m;i++){12         scanf("%d%d%d",&a,&b,&c);13         e[++hs]=(edge){b,h[a],c};14         h[a]=hs;15     }16     q[head++]=s;17     while(head>tail){18         a=q[tail++];19         for(int i=h[a];i;i=e[i].n){20             if(rel(v[e[i].s],v[a],e[i].v)){21                 q[head++]=e[i].s;22                 v[e[i].s]=v[a]+e[i].v;23             }24         }25     }26     for(int i=1;i<=n;i++) printf("%d ",v[i]);27     return 0;28 }

适用于各种找单源最短路的题目；

适用于负权图；

可以根据判断节点的入队次数来判断图是否有负权回路。eg：泥泞的道路

时间复杂度O(ke)，理论复杂度高于Dijkstra，但有玄学加速。eg：【模板】单源最短路径*

优化：

SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。

LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。

SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。

并未使用过，因为SPFA在时间上很优，一般不需要担心被卡常数。

 

Dijkstra

初始化最短路径表；

源点标记；

用源点的边松弛；

寻找距离最短的未被标记的点；

用这个点的边松弛；

如此循环n-1次。

 1 #include<cstdio> 2 int n,m,s,w[10010]; 3 int a,b,c; 4 bool v[10010]; 5 int h[10010],hs; 6 struct edge{int s,n,v;}e[500010]; 7 inline bool rel(long long x,long long y,long long z){return y+z<x?1:0;} 8 int main(){ 9     scanf("%d%d%d",&n,&m,&s);10     for(int i=1;i<=n;i++) if(i!=s) w[i]=2147483647;11     for(int i=1;i<=m;i++){12         scanf("%d%d%d",&a,&b,&c);13         e[++hs]=(edge){b,h[a],c};14         h[a]=hs;15     }16     v[s]=1;17     for(int i=h[s];i;i=e[i].n) if(rel(w[e[i].s],0,e[i].v)) w[e[i].s]=e[i].v;18     for(int k=1;k<n;k++){19         a=2147483647;20         for(int i=1;i<=n;i++) if(!v[i]&&w[i]<a) a=w[i],b=i;21         v[b]=1;22         for(int i=h[b];i;i=e[i].n) if(rel(w[e[i].s],w[b],e[i].v)) w[e[i].s]=e[i].v+w[b];23     }24     for(int i=1;i<=n;i++) printf("%d ",w[i]);25     return 0;26 }

！不能用于负权图。

一般在OI中不太常用；

时间复杂度O(n2)，理论上平均比SPFA更快，实际上被完虐了。。。

可以用堆优化，实现并不简单，然而优化效果也并不显然。

 

Bellman-Ford

时间复杂度O(ne)，这个效率在OI中寸步难行，SPFA是其优化版。
可以用于负权图，可以判断一个图中是否有负权回路。
 

最短路


联系
我们