备战蓝桥杯---图论之最短路Bellman-Ford算法及优化

目录

上次我们讲到复杂度为（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);
}