Bellman-Ford算法的核心是动态规划,前置知识,线性dp,非线性dp,树上dp
在搞这个算法之前,最好把dp搞熟悉
1.状态的定义
dist[n] 表示 起点1,到点n 的最短距离
2.状态的转移:每个点只可能由上一个经过的点到达。即一个基于归纳的思想
3.最不利构造,即考虑最最倒霉的情况,即考虑极端情况
比较好的情况下,假设其他点都更新了,那只要更新一条边和点即可
但是后面经过的点可能会回去,并且更新前面的点
最差的情况就是,每条边都要更新,所以考虑最差情况,每次更新所有边
for(int j=1;j<=eidx;j++){
int a = edges[j].from;
int b = edges[j].to;
int w = edges[j].weight;
if(dist[a]!=INF && dist[a]+w<dist[b]){
dist[b] = dist[a]+w;
}
}
最差的情况,1 到任意点,最多经过n-1条边
假设边的顺序情况最差,且1 到 n 需要经过n-1条边,即最差情况 ,那么至少需要迭代 n-1次 才能更新完所有的点
完整代码如下:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 3001;
const int MAXM = 30001;
const int INF = 9999999999;
struct Edge{
int from,to;
int weight;
};
Edge edges[MAXM*2];
int eidx;
int mat[MAXN][MAXN];
int dist[MAXN];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mat[i][j] = INF;
}
}
for(int i=1;i<=m;i++){
int a,b,w;
cin>>a>>b>>w;
//处理重边
mat[a][b]=mat[b][a]=min(mat[b][a],w);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mat[i][j]!=INF){
edges[++eidx].from = i;
edges[eidx].to = j;
edges[eidx].weight = mat[i][j];
}
}
}
//Bellman-Ford算法
fill(&dist[0],&dist[0]+n+1,INF);
dist[1] = 0;
for(int i=0;i<n-1;i++){
for(int j=1;j<=eidx;j++){
int a = edges[j].from;
int b = edges[j].to;
int w = edges[j].weight;
if(dist[a]!=INF && dist[a]+w<dist[b]){
dist[b] = dist[a]+w;
}
}
}
if(dist[n]>=INF){
cout<<-1<<endl;
}else{
cout<<dist[n]<<endl;
}
return 0;
}