小鱼在线网站建设,媒体门户网站建设方案,简单的网页设计作业,深圳外贸网站建设企业目录 上次我们讲到复杂度为#xff08;nm)logm(m为边#xff0c;n为点#xff09;的迪杰斯特拉算法#xff0c;其中有一个明显的不足就是它无法解决包含负权边的图。
于是我们引进Bellman-Ford算法。
核心#xff1a;枚举所有的点#xff0c;能松弛就松弛#xff0c;直…目录 上次我们讲到复杂度为nm)logm(m为边n为点的迪杰斯特拉算法其中有一个明显的不足就是它无法解决包含负权边的图。
于是我们引进Bellman-Ford算法。
核心枚举所有的点能松弛就松弛直到所有点都不能松弛。
具体过程
我们在外循环循环n-1(n为点数然后在内循环上枚举所有的边能松弛就松弛。
到这里肯定有许多人对它正确性怀疑其实我们可以知道在外循环循环k轮后k步以内可以到的点的值从源点在k步以内能走到的最优解有点类似广搜。
具体来说当k2时2步以内可以到的点的值2步内从源点走到该点的最小距离。的原因在于枚举边的时候可能会被刚刚更新的点在被更新一遍 上次我们讲到复杂度为nm)logm(m为边n为点的迪杰斯特拉算法其中有一个明显的不足就是它无法解决包含负权边的图。
于是我们引进Bellman-Ford算法。
核心枚举所有的点能松弛就松弛直到所有点都不能松弛。
具体过程
我们在外循环循环n-1(n为点数然后在内循环上枚举所有的边能松弛就松弛。
到这里肯定有许多人对它正确性怀疑其实我们可以知道在外循环循环k轮后k步以内可以到的点的值从源点在k步以内能走到的最优解有点类似广搜。
具体来说当k2时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代码
#includebits/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 dis1a.dis1;}
};
void merge(int x,int y,int v){edge[cnt].zhiv;edge[cnt].diany;edge[cnt].nexthead[x];head[x]cnt;
}
priority_queuety q;
queueint q1;
int dij(int s,int t){q.push({s,0});while(!q.empty()){ty ckq.top();q.pop();if(vis[ck.dian]1) continue;vis[ck.dian]1;for(int ihead[ck.dian];i!-1;iedge[i].next){int i1edge[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 hhq1.front();vis[hh]0;q1.pop();for(int ihead[hh];i!-1;iedge[i].next){int i1edge[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(){cinnm1st;memset(head,-1,sizeof(head));for(int i1;im1;i){scanf(%d%d%d,x,y,v);merge(x,y,v);merge(y,x,v);}memset(dis,0x3f,sizeof(dis));dis[s]0;coutspfa(s,t);
}
