图-贝尔曼福特（Bellman-Ford）算法详解（含全部代码）

目录适用条件基本操作函数功能实现函数测试使用图算法讲解初始化迭代贝尔曼福特算法代码全部代码实验结果适用条件图中可以有负权，但不能有负圈（圈中弧或边的权值之和小于0）基本操作函数InitGraph(Graph &G) 初始化函数参数：图G 作用：初始化图的顶点表，邻接矩阵等InsertNode(Graph ...

lady_killer9

17581人浏览 · 2019-10-24 17:46:42

lady_killer9 · 2019-10-24 17:46:42 发布

适用条件

图中可以有负权，但不能有负圈（圈中弧或边的权值之和小于0）

基本操作函数

InitGraph(Graph &G) 初始化函数参数：图G 作用：初始化图的顶点表，邻接矩阵等
InsertNode(Graph &G,VexType v) 插入点函数参数：图G,顶点v 作用：在图G中插入顶点v,即改变顶点表
InsertEdge(Graph &G,VexType v,VexType w) 插入弧函数参数：图G,某弧两端点v和w 作用：在图G两点v,w之间加入弧，即改变邻接矩阵
Adjancent(Graph G,VexType v,VexType w) 判断是否存在弧(v,w)函数参数：图G，某弧两端点v和w 作用：判断是否存在弧(v,w)
BFS(Graph G, int start) 广度遍历函数参数：图G,开始结点下标start 作用：宽度遍历
DFS(Graph G, int start) 深度遍历函数（递归形式）参数：图G,开始结点下标start 作用：深度遍历
Dijkstra(Graph G, int v) 最短路径 - Dijkstra算法参数：图G、源点v
Bellman_Ford(Graph G, int v) 最短路径 - Bellman_Ford算法参数：图G、源点v 作用：计算不含负圈图的最短路径返回是否有圈

功能实现函数

CreateGraph(Graph &G) 创建图功能实现函数参数：图G InsertNode 作用：创建图
BFSTraverse(Graph G) 广度遍历功能实现函数参数：图G 作用：宽度遍历
DFSTraverse(Graph G) 深度遍历功能实现函数参数：图G 作用：深度遍历
Shortest_Dijkstra(Graph &G) 调用最短路径-Dijkstra算法参数：图G、源点v
Shortest_Bellman_Ford(Graph &G) 调用最短路径- - Bellman_Ford算法参数：图G

测试使用图

算法讲解

迭代次数\目标结点	v0	v1	v2	v3	v4	pr
1	0	1	5	3	∞	pr[0]=-1,pr[1]=0 pr[2]=0,pr[3]=0 pr[4]=0
2	0	1	3	1	6	pr[0]=-1,pr[1]=0 pr[2]=1,pr[3]=2 pr[4]=3
3	0	1	3	-1	4	pr[0]=-1,pr[1]=0 pr[2]=1,pr[3]=2 pr[4]=3
4	0	1	3	-1	2	pr[0]=-1,pr[1]=0 pr[2]=1,pr[3]=2 pr[4]=3

多说一句，其中一个作者 Richard Bellman是动态规划的创始人，上面的表也就体现了动态规划的思想。下面的迭代部分红色部分就是状态转移方程（博主不喜欢用数学的符号化语言进行描述，一般都是理解了用文字来告诉读者）。

初始化

首次迭代结果，即与源点直连的边的权值，若无直连，则为无穷。

迭代

每次迭代都是与上一次迭代结果相比较。迭代次数即与源点之间的边数。迭代结果即min{上次迭代结果，边数增加后的权值之和}。

第二次迭代，目标节点为v2，从源点出发经过两条边到达v2时，最短路径（v0->v1->v2）长度变为3（1+2）。

目标节点为v3，从源点出发经过两条边到达v3时，最短路径（v0->v2->v3）长度变为1（5-4）。

目标节点为v4，从源点出发经过两条边到达v4时，最短路径（v0->v3->v4）长度变为6（3+3）。

第三次迭代，目标节点为v3，从源点出发经过三条边到达v3时，最短路径（v0->v1->v2->v3）长度变为-1（1+2-4）。

目标节点为v4，从源点出发经过三条边到达v4时，最短路径（v0->v2->v3->v4）长度变为4（5-4+3）。

第四次迭代，目标节点为v4，从源点出发经过四条边到达v4时，最短路径（v0->v1->v2->v3->v4）长度变为2（1+2-4+3）。

pr很简单，每次迭代更新就好，就不讲解了。

贝尔曼福特算法代码

//最短路径 - Bellman_Ford算法  参数：图G、源点v 作用：计算不含负圈图的最短路径 返回是否有圈
bool Bellman_Ford(Graph G, int v)
{
	//初始化
	int n = G.vexnum;//n为图的顶点个数
	for (int i = 0; i < n; i++)
	{
		D[i] = G.Edge[v][i];
		if (D[i] < INF)Pr[i] = v; //v与i连接，v为前驱
		else Pr[i] = -1;
	}
	D[v] = 0;
	//初始化结束，开始双重循环
	for(int i=2;i<G.vexnum-1;i++)
		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];
					Pr[k] = j;
				}
	//判断是否含有负圈
	bool flag = true;
	for (int j = 0; j<G.vexnum - 1; j++) //j为源点
		for (int k = 0; k<G.vexnum - 1; k++) //k为终点
			if (D[k] > D[j] + G.Edge[j][k])
			{
				flag = false;
				break;
			}
	return flag;
}

算法自带负圈检测，并且可知道负圈包含的节点。若含有负圈，则包含的点的最短路径值不收敛。

全部代码

/*
Project: 图-最短路径-Bellman-Ford算法（可含有负权弧）
Date:    2019/10/24
Author:  Frank Yu
基本操作函数:
InitGraph(Graph &G)             初始化函数 参数：图G 作用：初始化图的顶点表，邻接矩阵等
InsertNode(Graph &G,VexType v) 插入点函数 参数：图G,顶点v 作用：在图G中插入顶点v,即改变顶点表
InsertEdge(Graph &G,VexType v,VexType w) 插入弧函数 参数：图G,某弧两端点v和w 作用：在图G两点v,w之间加入弧，即改变邻接矩阵
Adjancent(Graph G,VexType v,VexType w) 判断是否存在弧(v,w)函数 参数：图G，某弧两端点v和w 作用：判断是否存在弧(v,w)
BFS(Graph G, int start) 广度遍历函数 参数：图G,开始结点下标start 作用：宽度遍历
DFS(Graph G, int start) 深度遍历函数（递归形式）参数：图G,开始结点下标start 作用：深度遍历
Dijkstra(Graph G, int v)  最短路径 - Dijkstra算法 参数：图G、源点v
Bellman_Ford(Graph G, int v)  最短路径 - Bellman_Ford算法  参数：图G、源点v 作用：计算不含负圈图的最短路径 返回是否有圈
功能实现函数：
CreateGraph(Graph &G) 创建图功能实现函数 参数：图G  InsertNode 作用：创建图
BFSTraverse(Graph G)  广度遍历功能实现函数 参数：图G 作用：宽度遍历
DFSTraverse(Graph G)  深度遍历功能实现函数 参数：图G 作用：深度遍历
Shortest_Dijkstra(Graph &G) 调用最短路径-Dijkstra算法 参数：图G、源点v
Shortest_Bellman_Ford(Graph &G) 调用最短路径- - Bellman_Ford算法  参数：图G
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<map>
#include<iterator>
#include<algorithm>
#include<iostream>
#define MaxVerNum 100 //顶点最大数目值
#define VexType char //顶点数据类型
#define EdgeType int //弧数据类型,有向图时邻接矩阵不对称，有权值时表示权值，没有时1连0不连
#define INF 0x3f3f3f3f//作为最大值
using namespace std;
//图的数据结构
typedef struct Graph
{
	VexType Vex[MaxVerNum];//顶点表
	EdgeType Edge[MaxVerNum][MaxVerNum];//弧表
	int vexnum, arcnum;//顶点数、弧数
}Graph;
//迪杰斯特拉算法全局变量
bool S[MaxVerNum]; //顶点集
int D[MaxVerNum];  //到各个顶点的最短路径
int Pr[MaxVerNum]; //记录前驱
//*********************************************基本操作函数*****************************************//
//初始化函数 参数：图G 作用：初始化图的顶点表，邻接矩阵等
void InitGraph(Graph &G)
{
	memset(G.Vex, '#', sizeof(G.Vex));//初始化顶点表
									  //初始化弧表
	for (int i = 0; i < MaxVerNum; i++)
		for (int j = 0; j < MaxVerNum; j++)
			G.Edge[i][j] = INF;
	G.arcnum = G.vexnum = 0;          //初始化顶点数、弧数
}
//插入点函数 参数：图G,顶点v 作用：在图G中插入顶点v,即改变顶点表
bool InsertNode(Graph &G, VexType v)
{
	if (G.vexnum < MaxVerNum)
	{
		G.Vex[G.vexnum++] = v;
		return true;
	}
	return false;
}
//插入弧函数 参数：图G,某弧两端点v和w 作用：在图G两点v,w之间加入弧，即改变邻接矩阵
bool InsertEdge(Graph &G, VexType v, VexType w, int weight)
{
	int p1, p2;//v,w两点下标
	p1 = p2 = -1;//初始化
	for (int i = 0; i<G.vexnum; i++)//寻找顶点下标
	{
		if (G.Vex[i] == v)p1 = i;
		if (G.Vex[i] == w)p2 = i;
	}
	if (-1 != p1&&-1 != p2)//两点均可在图中找到
	{
		G.Edge[p1][p2] = weight;//有向图邻接矩阵不对称
		G.arcnum++;
		return true;
	}
	return false;
}
//判断是否存在弧(v,w)函数 参数：图G，某弧两端点v和w 作用：判断是否存在弧(v,w) 
bool Adjancent(Graph G, VexType v, VexType w)
{
	int p1, p2;//v,w两点下标
	p1 = p2 = -1;//初始化
	for (int i = 0; i<G.vexnum; i++)//寻找顶点下标
	{
		if (G.Vex[i] == v)p1 = i;
		if (G.Vex[i] == w)p2 = i;
	}
	if (-1 != p1&&-1 != p2)//两点均可在图中找到
	{
		if (G.Edge[p1][p2] == 1)//存在弧
		{
			return true;
		}
		return false;
	}
	return false;
}
bool visited[MaxVerNum];//访问标记数组，用于遍历时的标记
//广度遍历函数 参数：图G,开始结点下标start 作用：宽度遍历
void BFS(Graph G, int start)
{
	queue<int> Q;//辅助队列
	cout << G.Vex[start];//访问结点
	visited[start] = true;
	Q.push(start);//入队
	while (!Q.empty())//队列非空
	{
		int v = Q.front();//得到队头元素
		Q.pop();//出队
		for (int j = 0; j<G.vexnum; j++)//邻接点
		{
			if (G.Edge[v][j] < INF && !visited[j])//是邻接点且未访问
			{
				cout << "->";
				cout << G.Vex[j];//访问结点
				visited[j] = true;
				Q.push(j);//入队
			}
		}
	}//while
	cout << endl;
}
//深度遍历函数（递归形式）参数：图G,开始结点下标start 作用：深度遍历
void DFS(Graph G, int start)
{
	cout << G.Vex[start];//访问
	visited[start] = true;
	for (int j = 0; j < G.vexnum; j++)
	{
		if (G.Edge[start][j] <INF && !visited[j])//是邻接点且未访问
		{
			cout << "->";
			DFS(G, j);//递归深度遍历
		}
	}
}
//最短路径 - Dijkstra算法 参数：图G、源点v3
void Dijkstra(Graph G, int v)
{
	//初始化
	int n = G.vexnum;//n为图的顶点个数
	for (int i = 0; i < n; i++)
	{
		S[i] = false;
		D[i] = G.Edge[v][i];
		if (D[i] < INF)Pr[i] = v; //v与i连接，v为前驱
		else Pr[i] = -1;
	}
	S[v] = true;
	D[v] = 0;
	//初始化结束,求最短路径，并加入S集
	for (int i = 1; i < n; i++)
	{
		int min = INF;
		int temp;
		for (int w = 0; w < n; w++)
			if (!S[w] && D[w] < min) //某点temp未加入s集，且为当前最短路径
			{
				temp = w;
				min = D[w];
			}
		S[temp] = true;
		//更新从源点出发至其余点的最短路径 通过temp
		for (int w = 0; w < n; w++)
			if (!S[w] && D[temp] + G.Edge[temp][w] < D[w])
			{
				D[w] = D[temp] + G.Edge[temp][w];
				Pr[w] = temp;
			}
	}
}
//最短路径 - Bellman_Ford算法  参数：图G、源点v 作用：计算不含负圈图的最短路径 返回是否有圈
bool Bellman_Ford(Graph G, int v)
{
	//初始化
	int n = G.vexnum;//n为图的顶点个数
	for (int i = 0; i < n; i++)
	{
		D[i] = G.Edge[v][i];
		if (D[i] < INF)Pr[i] = v; //v与i连接，v为前驱
		else Pr[i] = -1;
	}
	D[v] = 0;
	//初始化结束，开始双重循环
	for(int i=2;i<G.vexnum-1;i++)
		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];
					Pr[k] = j;
				}
	//判断是否含有负圈
	bool flag = true;
	for (int j = 0; j<G.vexnum - 1; j++) //j为源点
		for (int k = 0; k<G.vexnum - 1; k++) //k为终点
			if (D[k] > D[j] + G.Edge[j][k])
			{
				flag = false;
				break;
			}
	return flag;
}
//输出最短路径
void Path(Graph G, int v)
{
	if (Pr[v] == -1)
		return;
	Path(G, Pr[v]);
	cout << G.Vex[Pr[v]] << "->";
}
//**********************************************功能实现函数*****************************************//
//打印图的顶点表
void PrintVex(Graph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		cout << G.Vex[i] << " ";
	}
	cout << endl;
}
//打印图的弧矩阵
void PrintEdge(Graph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.Edge[i][j] == INF)cout << "∞ ";
			else cout << G.Edge[i][j] << " ";
		}
		cout << endl;
	}
}
//创建图功能实现函数 参数：图G  InsertNode 作用：创建图
void CreateGraph(Graph &G)
{
	VexType v, w;
	int vn, an;//顶点数，弧数
	cout << "请输入顶点数目:" << endl;
	cin >> vn;
	cout << "请输入弧数目:" << endl;
	cin >> an;
	cout << "请输入所有顶点名称:" << endl;
	for (int i = 0; i<vn; i++)
	{
		cin >> v;
		if (InsertNode(G, v)) continue;//插入点
		else {
			cout << "输入错误！" << endl; break;
		}
	}
	cout << "请输入所有弧（每行输入起点，终点及权值）:" << endl;
	for (int j = 0; j<an; j++)
	{
		int weight;
		cin >> v >> w >> weight;
		if (InsertEdge(G, v, w, weight)) continue;//插入弧
		else {
			cout << "输入错误！" << endl; break;
		}
	}
	cout << "图的顶点及邻接矩阵：" << endl;
	PrintVex(G);
	PrintEdge(G);
}
//广度遍历功能实现函数 参数：图G 作用：宽度遍历
void BFSTraverse(Graph G)
{
	for (int i = 0; i<MaxVerNum; i++)//初始化访问标记数组
	{
		visited[i] = false;
	}
	for (int i = 0; i < G.vexnum; i++)//对每个连通分量进行遍历
	{
		if (!visited[i])BFS(G, i);
	}
}
//深度遍历功能实现函数 参数：图G 作用：深度遍历
void DFSTraverse(Graph G)
{
	for (int i = 0; i<MaxVerNum; i++)//初始化访问标记数组
	{
		visited[i] = false;
	}
	for (int i = 0; i < G.vexnum; i++)//对每个连通分量进行遍历
	{
		if (!visited[i])
		{
			DFS(G, i); cout << endl;
		}
	}
}
//调用最短路径-Dijkstra算法 参数：图G
void Shortest_Dijkstra(Graph &G)
{
	char vname;
	int v = -1;
	cout << "请输入源点名称:" << endl;
	cin >> vname;
	for (int i = 0; i < G.vexnum; i++)
		if (G.Vex[i] == vname)v = i;
	if (v == -1)
	{
		cout << "没有找到输入点！" << endl;
		return;
	}
	Dijkstra(G, v);
	cout << "目标点" << "\t" << "最短路径值" << "\t" << "最短路径" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		if (i != v)
		{
			cout << "  " << G.Vex[i] << "\t" << "        " << D[i] << "\t";
			Path(G, i);
			cout << G.Vex[i] << endl;
		}
	}
}
//调用最短路径- - Bellman_Ford算法  参数：图G
void Shortest_Bellman_Ford(Graph &G)
{
	char vname;
	int v = -1;
	cout << "请输入源点名称:" << endl;
	cin >> vname;
	for (int i = 0; i < G.vexnum; i++)
		if (G.Vex[i] == vname)v = i;
	if (v == -1)
	{
		cout << "没有找到输入点！" << endl;
		return;
	}
	if (Bellman_Ford(G,v))
	{
		cout << "目标点" << "\t" << "最短路径值" << "\t" << "最短路径" << endl;
		for (int i = 0; i < G.vexnum; i++)
		{
			cout << "  " << G.Vex[i] << "\t" << "        " << D[i] << "\t";
			Path(G, i);
			cout << G.Vex[i] << endl;
		}
	}
	else
	{
		cout << "输入的图中含有负圈，不能使用该算法！" << endl;
	}
}
//菜单
void menu()
{
	cout << "************1.创建图       2.广度遍历******************" << endl;
	cout << "************3.深度遍历     4.迪杰斯特拉****************" << endl;
	cout << "************5.贝尔曼福特   6.退出**********************" << endl;
}
//主函数
int main()
{
	int choice = 0;
	Graph G;
	InitGraph(G);
	while (1)
	{
		menu();
		printf("请输入菜单序号：\n");
		scanf("%d", &choice);
		if (6 == choice) break;
		switch (choice)
		{
		case 1:CreateGraph(G); break;
		case 2:BFSTraverse(G); break;
		case 3:DFSTraverse(G); break;
		case 4:Shortest_Dijkstra(G); break;
		case 5:Shortest_Bellman_Ford(G); break;
		default:printf("输入错误！！！\n"); break;
		}
	}
	return 0;
}

实验结果

最短路径与生成树

实验结果截图

更多数据结构与算法实现：数据结构（严蔚敏版）与算法的实现（含全部代码）

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。

尧米AI

尧米是由西云算力与CSDN联合运营的AI算力和模型开源社区品牌，为基于DaModel智算平台的AI应用企业和泛AI开发者提供技术交流与成果转化平台。

更多推荐

一文熟悉新版llama.cpp使用并本地部署LLAMA

尧米AI

Jxls异常 Cannot load XLS transformer. Please make sure a Transformer impleme

错误：Cannot load XLS transformer. Please make sure a Transformer implementation is in classpath原因：这是 jxls 的版本升级2.4后需要额外导入其他依赖<dependency><groupId>org.jxls</groupId><artifactId>j