最短路径算法

Floyd算法

运用了动态规划思想

#includeusing namespace std;int main(){int n;cin>>n;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;jg[i][k]+g[k][j])g[i][j]=g[i][k]+g[k][j];}}}}

时间复杂度过高( O 3 O^3 O3)，只使用于n≤100的数据。

时间复杂度：( O3 O^3 O3)

空间复杂度：( O2 O^2 O2)

算法特点：解决多源最短路径的问题

局限性：能够处理负边权的图，但是不能处理含负环的图（负环不存在最短路径）

Dijkstra算法

基于贪心思想

基本思想：通过贪心思想找出距离源点最近的顶点，再通过该顶点去作为中转顶点来找到下一个距离源点最近的顶点，如此反复直到所有的顶点到源点的距离都被确定。

用数组$dis[i]$表示从源点到i的距离，$vis[i]$表示是否访问过i节点。

dis[]和vis[]初始化：

dis[i]=a[1][i];dis[1]=0;vis[1]=1;

松弛算法：

if(dis[G]>dis[F]+a[F][G])    dis[G]=dis[F]+a[F][G];

代码：

#includeusing namespace std;int n,m;int a[105][105];int dis[10005];int vis[105];int s1,t;int main(){memset(a,0x3f,sizeof(a));cin>>n>>m;for(int i=1;i>x>>y>>z;a[x][y]=z;a[y][x]=z;}cin>>s1>>t;for(int i=1;i<n;i++)dis[i]=a[s1][i];dis[s1]=0;vis[s1]=1;for(int i=1;i<=n;i++){int Min=0x3f3f3f3f;int s;for(int j=1;j<=n;j++){if(dis[j]<Min&&vis[j]==0){Min=a[s1][j];s=j;}}vis[s]=1;for(int j=1;j<=n;j++){if(vis[j]==0){dis[j]=min(dis[j],dis[s]+a[s][j]);}}}cout<<dis[t];return 0;}

可以使用堆优化，即用priority_queue储存，依次选取离源点的最小值进行操作

见：Dijkstra堆优化 - CaptainLi - 博客园 (cnblogs.com)

beel-man ford

#includeusing namespace std;#define inf 100000000struct edge{int x,y,z;}edge[101];int n,e,dis[101];int main(){cin>>n>>e;for(int i=1;i>edge[i].x>>edge[i].y>>edge[i].z;for(int i=1;i<=n;i++)dis[i]=inf;dis[1]=0;for(int i=1;i<=n-1;i++){bool done=0;for(int j=1;jdis[edge[i].x]+edge[i].z){dis[edge[i].y]=dis[edge[i].x]+edge[i].z;done=1;}}if(done==0)break;}}

SPFA

SPFA算法是Beelman-Ford算法的队列优化算法，通常用于求解含负边权的单源最短路径，以及判断负环。在最坏情况下，SPFA算法的时间复杂度和空间复杂度和Bellman-Ford算法相同，为$O(nm)$，但在稀疏图上运行效率较高。

思路：

1. 数据结构。链式前向星存储图，$dis[i]$记录从源点到节点i的最短路径长度，$vis[i]$标记节点i是否在队列中，$sun[i]$记录节点i的入队次数。
2. 创建一个队列，源点u入队，标记u在队列中，u的入队次数加1.
3. 松弛操作。取出队头x，标记x不在队列中。考察x的所有出边$i(x,v,w)$，如果$dis[v]>dis[x]+e[i].w$，则$dis[i]=dis[x]+e[i].w$。如果节点v不在队列中，如果v的入队次数+1后≥n，则说明有负环，退出；否则v入队，标记v在队列中。
4. 重复松弛操作，直至队列为空。

链式前向星存储：

int cnt=0;struct edge{int to;int dis;int next;}edge[105];void addedge(int from,int to,int dis){edge[++cnt].next=head[from];edge[cnt].to=to;edge[cnt].dis=dis;head[from]=cnt;}

代码：

#includeusing namespace std;int cnt=0;int vis[105];int dis[105];int sum[105];int head[105];int n;struct edge{int to;int dis;int next;}edge[105];void addedge(int from,int to,int dis){edge[++cnt].next=head[from];edge[cnt].to=to;edge[cnt].dis=dis;head[from]=cnt;}bool spfa(int u){queueq;memset(vis,0,sizeof(vis));memset(sum,0,sizeof(sum));memset(dis,0x3f,sizeof(dis));dis[u]=0;vis[u]=1;sum[u]++;q.push(u);while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=head[x];i;i=edge[i].next){int v=edge[i].to;if(dis[v]>dis[x]+edge[i].dis){dis[v]=dis[x]+edge[i].dis;if(!vis[v]){if(++sum[v]>=n)return true;//负环退出vis[v]=1;q.push(v);}}}}return false;}int main(){cin>>n;int u,t;cin>>u>>t;if(!spfa(u))cout<<dis[t];elsecout<<"负环";return 0;}

时间复杂度：最坏情况下是$O(nm)$，对于稀疏图时间复杂度为$O(km)$，k为一个较小常数

空间复杂度：包含数组edge[]，dist[]，空间复杂度为$O(n+m)$

优势：可以判断负环

算法优化

SLF优化

SLF策略(small label first)：如果待入队节点是j，队首元素为节点i，若$dis[j]<dis[i]$，则将j插入队首，否则插入队尾。

LLL优化

LLL策略(large label last)：设队首元素为节点i，队列中所有dis[]的平均值为x，若$dis[i]>x$，则将节点插入队尾，查找下一元素，直到某一节点i满足$dis[i]\le x$，将节点i出队，进行松弛操作。

SLF和LLL在随机数据上表现优秀，但是在正权图上最坏情况为$O(nm)$，在负权图上的最坏情况为达到指数级复杂度。

最短路径算法比较：几大最短路径算法比较_shiwei408的博客-CSDN博客