深圳大眼睛网站建设,seo服务器多ip,网站开发类,弹出网站代码介绍
全称Bellman-Ford算法#xff0c;目的是求解有负权边的最短路径问题。 考虑环#xff0c;根据环中边的边权之和的正负#xff0c;将环分为零环、正环、负环。其中零环、正环不会影响最短路径的求解#xff0c;而负环会影响最短路径的求解。 可用BF算法返回一个bool值…介绍
全称Bellman-Ford算法目的是求解有负权边的最短路径问题。 考虑环根据环中边的边权之和的正负将环分为零环、正环、负环。其中零环、正环不会影响最短路径的求解而负环会影响最短路径的求解。 可用BF算法返回一个bool值来判断是否有负环如果有返回false,否则返回true.
bool BF(int b){fill(path,pathmaxn,INF);path[b]0;//求最短距离for(int i0;in-1;i){//比较趟数for(int j0;jn;j){//遍历每一个顶点相关的邻接边for(int k0;ktable[j].size();k){int vtable[j][k].v;int valuetable[j][k].value;if(path[j]valuepath[v]){//此时path[v]应该是最小距离path[v]path[j]value;}}}//判断是否有负环有返回false,无返回truefor(int m0;mn;m){//再次遍历边时for(int k0;ktable[m].size();k){int vtable[m][k].v;int valuetable[m][k].value;if(path[m]valuepath[v])//还能找到有比path[v]更小的距离return false;//说明有负环存在}}return true;//否则无负环}
}设计思想
将求最短路径看作是求以源点为根结点的一棵最短路径树此时图与起点均确定因此最短路径树也就确定了且最短路径树的层数一定不超过顶点个数V即树中两顶点的比较更新次数不超过V-1轮。
实现
由于用邻接矩阵遍历边时复杂度会达到O(V的3次方)因此我们使用邻接表去实现
应用
由于求最短路径条数时BF算法会重复遍历相同的顶点因此在有多条最短路径数时最短路径条数的累加会出错。于是我们想到用set容器记录前驱结点通过遍历去重后的前驱结点进行累加。 set容器的介绍
#include iostream
#include vector
#include set
#include algorithm
using namespace std;
const int maxn100;
const int INF1000000000;
struct node{int v;//邻接顶点int value;//对应边权//通过构造函数实现定义同时初始化node(int a,int b):v(a),value(b){}
};
vectornode table[maxn];
int n,edge,st,ed,weight[maxn];int path[maxn],num[maxn],w[maxn];
setint pre[maxn];//记录前驱以便去重void BF(int b){fill(path,pathmaxn,INF);memset(num,0,sizeof(num));memset(w,0,sizeof(w));path[b]0;w[b]weight[b];num[b]1;for(int i0;in-1;i){for(int j0;jn;j){for(int k0;ktable[j].size();k){//记录int vtable[j][k].v;int valuetable[j][k].value;if(path[j]valuepath[v]){path[v]path[j]value;w[v]w[j]weight[v];num[v]num[j];//小于覆盖pre[v].clear();//清空pre[v].insert(j);//记录最短路径前驱}else if(path[j]valuepath[v]){if(w[v]w[j]weight[v])w[v]w[j]weight[v];pre[v].insert(j);//继续记录num[v]0;//防止重复计数清空//重新累加计数:通过遍历前驱结点实现for( setint::iterator itpre[v].begin();it!pre[v].end();it)num[v]num[*it];//*itpre[j][k],即k的前驱}}}}}int main(){int v1,v2,weigh;cinnedgested;for(int i0;in;i)cinweight[i];for(int j0;jedge;j){//构建邻接表cinv1v2weigh;table[v2].push_back(node(v1,weigh));table[v1].push_back(node(v2,weigh));}BF(st);coutnum[ed] w[ed]endl;return 0;
}
