贝尔曼福特算法

提示：功不唐捐，玉汝于成，岁月不负有心人

文章目录

• 前言
• 分析
• *** 作过程
• 负圈判断
• 代码汇总
• 运行截图
• 注意
• 总结

---

前言

松弛的理解
建议大家先看一下 ！！！

分析

贝尔曼福特就像前面的迪杰斯特拉class="superseo">算法一样 ，理解起来是有难度的，但是，写出来倒不是那么难。 前面我们知道不能处理负权的一个主要原因是 迪杰斯特拉每一次进来一个新的结点 ，都是对此结点直接关联的结点并且没有加入结果集中的结点进行松弛处理，这里贝尔曼福特的方式 每一次选取一个新的结点之后，都是对所有的边进行松弛处理，那么要经过多少次对所有边的松弛处理呢？最多不过V-1 为什么是V-1 假设极端状态下就是一个链表的形式，其中就是V-1

*** 作过程

知道上面这些我们就可以写出代码了，主要是这三个for
内层的两个for:j,k 表示的就是遍历所有的边 最外层的for：i 表示就是所有边的松弛的次数

	for(int i=0;i<G.vexnum-1;i++){//表示所有边松弛的次数最多n-1
		for(int j=0;j<G.vexnum;j++){ //j为源点
			for(int k=0;k<G.vexnum;k++){//k为终点
				if (D[k] > D[j] + G.Edge[j][k])
				{
					D[k] = D[j] + G.Edge[j][k];
				}
			}
		}
	}

负圈判断

再进行一次全局伸缩判断是否继续变化

for (int j = 0; j<G.vexnum - 1; j++){
		for (int k = 0; k<G.vexnum - 1; k++){
			if (dict[k] > dict[j] + G.arcs[j][k])
			{
				cout<<"存在负圈，上述路径求取不准确"<<endl;
				return; 
			}	
			
		} 
	}

代码汇总

代码78 行for(int i=2;i

#include
using namespace std;
#define MaxInt 32767  //表示极大值∞  其实就是一种无穷标志
#define MVNum  100    //表示最大顶点数 
typedef char VerTexType;//假设顶点的数据结构类型为char 
typedef int  ArcType;//假设权值类型为整形
//下面的是邻接矩阵的 
typedef struct{
	 VerTexType vexs[MVNum];//顶点表 
	 ArcType  arcs[MVNum][MVNum];//邻接矩阵 
	 int vexnum;//图的当前顶点数
	 int arcnum;//图的当前边数
}AMGraph;
//打印邻接矩阵 
void PrintAMG(AMGraph G){
	cout<<" "<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" "; 
		for(int j=0;j<G.vexnum;j++){
			cout<<G.arcs[i][j]<<" ";
		}
		cout<<endl;
	}
} 
//创建一个无向图 ，其实就是填充两个数组 
void CreateAdjoin(AMGraph &G){
	cout<<"请输入顶点数和边数"<<endl;
	cin>>G.vexnum>>G.arcnum; 
	cout<<"请输入各个顶点名称"<<endl; 
	for(int i=0;i<G.vexnum;i++){
		cin>>G.vexs[i]; 
	}
	for(int h=0;h<G.arcnum;h++){
		char vex1;char vex2;
		cout<<"请输入弧的两个顶点"<<endl;
		cin>>vex1>>vex2; 
		//首先来看是否存在这两个顶点  若是存在则找到这两个点对应的下标
		// 当然创建的时候一种更加简单的方式就是遍历二维数组 一个一个输入
		int i=0;while(G.vexs[i++]!=vex1);
		int j=0;while(G.vexs[j++]!=vex2);
		if(i>G.vexnum||j>G.vexnum){//没有找到 
			cout<<"你输入的结点值不正确"<<endl; 
		}
		else{
			cout<<"请输入此边对应的权重"<<endl; 
			cin>>G.arcs[i-1][j-1];
			//G.arcs[j-1][i-1]=G.arcs[i-1][j-1];
		}
	}
	PrintAMG(G);
}
/**/ 
void Bellman(AMGraph &G){ 
	int dict[G.vexnum];//用来存储最短距离 
	//因为之前若是没有边 放的是0  这里将0 修改成MaxInt 
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i!=j&&0==G.arcs[i][j]){
				G.arcs[i][j]=MaxInt;
			}
		}
	}
	//初始化 
	for(int i=0;i<G.vexnum;i++){ 
		dict[i]=G.arcs[0][i];//初始化dict[] 
	} 
	//将源点加入到最优点中 
	dict[0]=0;
	cout<<"此时的dict数组是"<<endl; 
		for(int i=0;i<G.vexnum;i++){ 
		cout<<dict[i]<<" ";
		}
		cout<<endl;
	for(int i=2;i<G.vexnum-1;i++){
		for(int j=0;j<G.vexnum;j++){ // 这个for 及内层的for指的是所以的边j为源点
			for(int k=0;k<G.vexnum;k++){//k为终点
				if (dict[k] > dict[j] + G.arcs[j][k])
				{
					dict[k] = dict[j] + G.arcs[j][k];
				}
			}
		}
		cout<<"此时的dict数组是"<<endl; 
		for(int i=0;i<G.vexnum;i++){ 
		cout<<dict[i]<<" ";
		}
		cout<<endl; 
	}
	//判断是否含有负圈  再进行一波全局伸缩判断是否变化  
	for (int j = 0; j<G.vexnum - 1; j++){
		for (int k = 0; k<G.vexnum - 1; k++){
			if (dict[k] > dict[j] + G.arcs[j][k])
			{
				cout<<"存在负圈，上述路径求取不准确"<<endl;
				return; 
			}	
			
		} 
	}
	
}
int main(){
	AMGraph G;
	CreateAdjoin(G);
	Bellman(G); 
}

运行截图

使用的测试用图

注意

其实输入的时候之前使用的是邻接矩阵 存储数据，这里需要需要存储有向图才能进行 *** 作(这里需要将51行注释掉 感兴趣的读者可以同样的输入 去除注释会是什么结果)，因为无向图的某一个边若是负值 其实就是相当于是负圈 求得dict数组也就不准确 所以个人的愚见 ，负无向图不能使用贝尔曼福特算法！！！
若是不注销效果截图

当然也可以优化 比如dict 没有变化的时候就跳出，比如设置一个pre数组什么的 这里就不写了

总结

其实写出来是不难的 主要是理解 是有一定难度的 感觉不错点个赞呗 铁子！！