一:Bellman_Ford
1:Dijkstra并不能解决带有负权边的图。
而Bellman_Ford算法可以。
2:核心代码:
for(int i=1;i<=n-1;i++) { for(int j=1;j<=m;j++) { dis[v[j]]=min(dis[v[j]],backup[u[j]]+w[j]); } }
3:依然是熟悉的松弛操作,但这里是从部分扩大到全局。每次只松弛一部分。
第1轮,得到从1号顶点"只能经过一条边"到达其余各顶点的最短路径长度。
第2轮,得到从1号顶点"只能经过两条边"到达其余各顶点的最短路径长度。
.......
第k轮,就是"经过k条边"
在一个含有n个顶点的图中,任意两点之间的最短路径最多包含n-1条边
所以最外层只需要循环n-1就可以了。
注意:这里的前提是,此时无正负权回路,因为最短路径一定是一个不包含回路的简单路径。
4:板子:
有边数限制的最短路:https://www.cnblogs.com/liyexin/p/14025379.html
判负环:https://www.cnblogs.com/liyexin/p/14026646.html
二:SPFA
1:对Bellman_Ford的优化版本。最坏情况下复杂度和Bellman-Ford 相同,为 O(VE)。
Bellman_Ford中很多松弛操作都是没有必要。
SPFA每次选取队首顶点u,对顶点u的所有出边进行松弛操作。其实思想就是,一个点被更新,那么它的邻居结点就有被更新的机会,所以可以把它们加入队列,没更新的点,自然没有机会进队列。
记得引入判重操作,防止一个点在队列中同时出现多次。
2:板子:
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stack> using namespace std; typedef long long ll; const int maxn=1e5+10; const int inf=0x3f3f3f3f; int e[maxn],ne[maxn],h[maxn],idx,w[maxn]; int dis[maxn],vis[maxn]; int n,m; void init() { memset(h,-1,sizeof(h)); memset(dis,inf,sizeof(dis)); dis[1]=0; } void add(int a,int b,int c) { w[idx]=c; e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } int spfa() { queue<int>q; q.push(1); vis[1]=1; while(!q.empty()) { int t=q.front(); q.pop(); vis[t]=0; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; if(vis[j]==0) { q.push(j); } } } } if(dis[n]>inf/2) return -1; return dis[n]; } int main() { init(); cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } int t=spfa(); if(t==-1) cout<<"impossible"<<endl; else cout<<t<<endl; }