目录
上次我们讲到复杂度为(n+m)logm(m为边,n为点)的迪杰斯特拉算法,其中有一个明显的不足就是它无法解决包含负权边的图。
于是我们引进Bellman-Ford算法。
核心:枚举所有的点,能松弛就松弛,直到所有点都不能松弛。
具体过程:
我们在外循环循环n-1(n为点数),然后在内循环上枚举所有的边,能松弛就松弛。
到这里,肯定有许多人对它正确性怀疑,其实,我们可以知道,在外循环循环k轮后,k步以内可以到的点的值<=从源点在k步以内能走到的最优解(有点类似广搜)。
具体来说,当k=2时,2步以内可以到的点的值<=2步内从源点走到该点的最小距离。(<=的原因在于枚举边的时候可能会被刚刚更新的点在被更新一遍)
上次我们讲到复杂度为(n+m)logm(m为边,n为点)的迪杰斯特拉算法,其中有一个明显的不足就是它无法解决包含负权边的图。
于是我们引进Bellman-Ford算法。
核心:枚举所有的点,能松弛就松弛,直到所有点都不能松弛。
具体过程:
我们在外循环循环n-1(n为点数),然后在内循环上枚举所有的边,能松弛就松弛。
到这里,肯定有许多人对它正确性怀疑,其实,我们可以知道,在外循环循环k轮后,k步以内可以到的点的值<=从源点在k步以内能走到的最优解(有点类似广搜)。
具体来说,当k=2时,2步以内可以到的点的值<=2步内从源点走到该点的最小距离。(<=的原因在于枚举边的时候可能会被刚刚更新的点在被更新一遍)
因此,在n-1轮后,因为每一个点最多被走一次(除非是负环,等下讨论),因此,利用上述结论,我们可以得出在外循环循环n-1轮后,所有的点的值为从源点出发走到的最优解。
下面我们讨论一下负环,其实,如果出现负环,最短路就应该为负无穷,我们为了判断负环,只要比较更新次数有无<=n-1即可。
因为这过于暴力,复杂度为o(n*m),基本一用就寄,于是我们考虑一下优化
我们不妨思考一个问题(这也是优化的关键)
一个点在什么情况下可以优化?
显然,只有到它的前一个点它的值优化改变后,那个点才可能被优化。因为边权是不变的,而前一个点它的值无法被优化时,dis[a]=map[a][b]+dis[b],相当于dis[b]不变,那么dis[a]肯定也不变。
在知道这个后,我们让dis[源点]=0,其他为极大值。
我们对于边的枚举,只要枚举上一次被更新的点的边就可以了。
我们用队列实现(即SPFA算法,复杂度为o(k*m)(k为每一个点入队的平均次数)
还是这一题,我们用这个方法实现一下。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
struct node{int zhi;int dian;int next;
}edge[20010];
int dis[1010],head[1010],cnt,n,m1,s,t,x,y,v;
bool vis[1010];
struct ty{int dian,dis1;bool operator<(const ty &a) const{return dis1>a.dis1;}
};
void merge(int x,int y,int v){edge[++cnt].zhi=v;edge[cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
priority_queue<ty> q;
queue<int> q1;
int dij(int s,int t){q.push({s,0});while(!q.empty()){ty ck=q.top();q.pop();if(vis[ck.dian]==1) continue;vis[ck.dian]=1;for(int i=head[ck.dian];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(vis[i1]==1) continue;if(dis[i1]>dis[ck.dian]+edge[i].zhi){dis[i1]=dis[ck.dian]+edge[i].zhi;q.push({i1,dis[i1]});}}}if(dis[t]>=0x3f3f3f3f) return -1;else return dis[t];
}
int spfa(int s,int t){q1.push(s);while(!q1.empty()){int hh=q1.front();vis[hh]=0;q1.pop();for(int i=head[hh];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(dis[i1]>dis[hh]+edge[i].zhi){dis[i1]=dis[hh]+edge[i].zhi;if(vis[i1]==0){vis[i1]=1;q1.push(i1);}}}}if(dis[t]>=0x3f3f3f3f) return -1;else return dis[t];
}
int main(){cin>>n>>m1>>s>>t;memset(head,-1,sizeof(head));for(int i=1;i<=m1;i++){scanf("%d%d%d",&x,&y,&v);merge(x,y,v);merge(y,x,v);}memset(dis,0x3f,sizeof(dis));dis[s]=0;cout<<spfa(s,t);
}