【算法导论】单源最短路径之Bellman-Ford算法

简介:         单源最短路径指的是从一个顶点到其它顶点的具有最小权值的路径。我们之前提到的广度优先搜索算法就是一种无权图上执行的最短路径算法,即在所有的边都具有单位权值的图的一种算法。

        单源最短路径指的是从一个顶点到其它顶点的具有最小权值的路径。我们之前提到的广度优先搜索算法就是一种无权图上执行的最短路径算法,即在所有的边都具有单位权值的图的一种算法。单源最短路径算法可以解决图中任意顶点间的最短路径。

        对于单源最短路径问题,一般有两种经典解法:1.对于有权值为负的图,采用Bellman-Ford算法;2.对于权值全为正的图,常采用Dijkstra算法。本文介绍Bellman-Ford算法,下一篇介绍Dijkstra算法。

Bellman-Ford算法适用于权值可以为负、无权值为负的回路的图,这比Dijkstra算法的使用范围要广。其基本思想为:首先假设源点到所有点的距离为无穷大,然后从任一顶点u出发,遍历其它所有顶点vi,计算从源点到其它顶点vi的距离与从vi到u的距离的和,如果比原来距离小,则更新,遍历完所有的顶点为止,即可求得源点到所有顶点的最短距离。下面用实例说明:



上图中,顶点内的值表示该顶点到s顶点的距离。在下面的具体程序实现中,我用0 1 2 3 4代表 s t x y z.

具体程序实现如下:

#include<stdio.h>
#define M 10//边数
#define N 5//顶点数
#define MAX 10000

int BellmanFord(int dist[N][N],int d[N],int i);

int flag1=0;
int flag2=0;

typedef struct
{
	int startvex;
	int endvex;
	int length;
}edge;
edge T[M];
void main()
{
	int dist[N][N]={{0,6,MAX,7,MAX},
					{MAX,0,5,8,-4},
					{MAX,-2,0,MAX,MAX},
					{MAX,MAX,-3,0,9},
					{2,MAX,7,MAX,0}};//图的邻接矩阵
	int d[N];
	int num=0;
    num=BellmanFord(dist,d, 0);//计算下标为0的顶点到其它顶点的距离,num用于统计边数
	for(int i=0;i<N;i++)//打印到各个顶点之间的距离
		printf("%d ",d[i]);
	printf("\n");
	for(int j=0;j<num;j++)//打印考虑过的边
		printf("start=%d,end=%d,lenth=%d\n",T[j].startvex,T[j].endvex,T[j].length);
}

int BellmanFord(int dist[N][N],int d[N],int i)
{
	for(int j=0;j<N;j++)//初始化
		d[j]=MAX;
	d[i]=0;
	int num=0;

	for(int k=0;k<N-1;k++)
	{
		for(int ii=0;ii<N;ii++)
			for(int jj=0;jj<N;jj++)
			{
				if(dist[ii][jj]!=MAX)
				{
					if(d[jj]>(d[ii]+dist[ii][jj]))//不断更新距离
					{
						d[jj]=d[ii]+dist[ii][jj];//当原节点到jj节点的距离大于
						                         //原节点到ii节点的距离与从ii节点到jj节点的距离和时更新
						T[num].startvex=ii;
						T[num].endvex=jj;
						T[num].length=dist[ii][jj];
						num++;
					}
				}
			}
	}
	for(int ii=0;ii<N;ii++)
	for(int jj=0;jj<N;jj++)//有权值为负的回路的情况
	{
		if(d[jj]>(d[ii]+dist[ii][jj]))
			return 0;
	}
return num;

}

结果显示如下:



注意:上述的结果与前面图解的一致,但是用到的边有7条比前面图解的阴影部分的边多3条,这是因为图解过程中省略了中间的一些步骤,直接得到最小权值时的情况。通过阴影部分的边,我们可以轻松的找到最短路径所经过的顶点,当然,当图比较复杂时,就该写程序来打印最短路径了。


注:如果程序出错,可能是使用的开发平台版本不同,请点击如下链接: 解释说明


原文:http://blog.csdn.net/tengweitw/article/details/17451125

作者:nineheadedbird


目录
相关文章
|
22天前
|
存储 算法 测试技术
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
|
22天前
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
5月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
135 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
7月前
|
自然语言处理 算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
88 0
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
|
2天前
|
机器学习/深度学习 资源调度 算法
基于入侵野草算法的KNN分类优化matlab仿真
本程序基于入侵野草算法(IWO)优化KNN分类器,通过模拟自然界中野草的扩散与竞争过程,寻找最优特征组合和超参数。核心步骤包括初始化、繁殖、变异和选择,以提升KNN分类效果。程序在MATLAB2022A上运行,展示了优化后的分类性能。该方法适用于高维数据和复杂分类任务,显著提高了分类准确性。
|
3天前
|
算法 数据安全/隐私保护 计算机视觉
基于sift变换的农田杂草匹配定位算法matlab仿真
本项目基于SIFT算法实现农田杂草精准识别与定位,运行环境为Matlab2022a。完整程序无水印,提供详细中文注释及操作视频。核心步骤包括尺度空间极值检测、关键点定位、方向分配和特征描述符生成。该算法通过特征匹配实现杂草定位,适用于现代农业中的自动化防控。
|
5天前
|
资源调度 算法 数据可视化
基于IEKF迭代扩展卡尔曼滤波算法的数据跟踪matlab仿真,对比EKF和UKF
本项目基于MATLAB2022A实现IEKF迭代扩展卡尔曼滤波算法的数据跟踪仿真,对比EKF和UKF的性能。通过仿真输出误差收敛曲线和误差协方差收敛曲线,展示三种滤波器的精度差异。核心程序包括数据处理、误差计算及可视化展示。IEKF通过多次迭代线性化过程,增强非线性处理能力;UKF避免线性化,使用sigma点直接处理非线性问题;EKF则通过一次线性化简化处理。
|
5天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于生物地理算法的MLP多层感知机优化matlab仿真
本程序基于生物地理算法(BBO)优化MLP多层感知机,通过MATLAB2022A实现随机数据点的趋势预测,并输出优化收敛曲线。BBO模拟物种在地理空间上的迁移、竞争与适应过程,以优化MLP的权重和偏置参数,提升预测性能。完整程序无水印,适用于机器学习和数据预测任务。
|
6天前
|
算法 数据安全/隐私保护
基于二次规划优化的OFDM系统PAPR抑制算法的matlab仿真
本程序基于二次规划优化的OFDM系统PAPR抑制算法,旨在降低OFDM信号的高峰均功率比(PAPR),以减少射频放大器的非线性失真并提高电源效率。通过MATLAB2022A仿真验证,核心算法通过对原始OFDM信号进行预编码,最小化最大瞬时功率,同时约束信号重构误差,确保数据完整性。完整程序运行后无水印,展示优化后的PAPR性能提升效果。
|
8天前
|
算法 数据安全/隐私保护
基于Adaboost的数据分类算法matlab仿真
本程序基于Adaboost算法进行数据分类的Matlab仿真,对比线性与非线性分类效果。使用MATLAB2022A版本运行,展示完整无水印结果。AdaBoost通过迭代训练弱分类器并赋予错分样本更高权重,最终组合成强分类器,显著提升预测准确率。随着弱分类器数量增加,训练误差逐渐减小。核心代码实现详细,适合研究和教学使用。

热门文章

最新文章