文章/答案/技术大牛

发布

社区首页 >专栏 >【狂热算法篇】探寻图论幽径：Bellman - Ford 算法的浪漫征程（通俗易懂版）

【狂热算法篇】探寻图论幽径：Bellman - Ford 算法的浪漫征程（通俗易懂版）

用户11458826

发布于 2025-04-01 01:08:04

13202

代码可运行

文章被收录于专栏：杀马特杀马特

运行总次数：2

代码可运行

本篇带大家探究的是Bellman-Ford算法；从基本理解，画图分析展示，再到最后的代码实现，以及为何要这样实现代码，等一些细节问题做解释，相关题型应用，非常值得哟，尤其是刚入门的小白学习；干货满满，通俗易懂；欢迎大家点赞收藏阅读呀！！！

一·本算法背景：

在图论与计算机科学领域，求解最短路径问题是一个基础且关键的任务，它在众多实际场景中有着广泛的应用，如交通路线规划、通信网络优化、物流配送路径选择等。Bellman - Ford 算法作为一种经典的单源最短路径算法，能够在存在负权边的图中找到从源点到其他各顶点的最短路径，或判断图中是否存在负权回路，在解决复杂网络路径问题时发挥着重要作用。

但是它不像我们的FLoyd算法一样是多源可以求出每个点到某个点的最短路径；相比之下对dijkstra算法而下可以处理负边权（但都对负边环没办法）。

Floyd传送门：【狂热算法篇】探秘图论之 Floyd 算法：解锁最短路径的神秘密码(通俗易懂版)-CSDN博客

dijkstra传送门：【狂热算法篇】探秘图论之Dijkstra 算法：穿越图的迷宫的最短路径力量（通俗易懂版）-CSDN博客

二·算法核心思想及实例模拟操作：

Bellman - Ford 算法基于松弛操作的思想。

松弛操作是指对图中每条边所连接的两个顶点的距离进行比较和更新，尝试找到更短的路径。

其核心在于不断尝试通过其他顶点来缩短源点到目标顶点的距离，直到无法再进行优化或者确定存在负权回路。

从直观上理解，就像在一个地图（图）中，我们要从一个起点（源点）到达各个目的地（其他顶点），每次检查所有可能的路线（边），看是否能通过经过某个中间地点（中间顶点）来缩短从起点到目的地的距离。

说白了；就是对所有的边进行n-1次松弛操作；就可以把最终的源点到每个点的最短源点距更新出来。

个人认为相比上面的两个算法而言它更侧重于边；即我们每次是按照边为主来保存它的起始点，终止点，以及权重（也就是下面我们按照边给它封装成了类）。

这里我们还是需要三张表来记录，某点到源点的最短路径dist；边的相关信息；记录前驱结点方便找最短路径：

dist	edge	pre
某点到源点的最短路径dist	边的相关信息	记录某点前驱结点
以数组为例	设计成了结构体	数组为例

下面根据上面说的核心步骤；我们举例子来模拟一下：

储存edge的相关信息表：

u（起始点）	v（终止点）	w(边权)
1	3	-2
3	2	3
2	1	2
1	2	5

下面我们就根据表对它n-1次松弛：

三.算法详细步骤:

下面我们分四步来对代码进行差分过程；进行相关代码剖析书写操作：

3.1初始化：

这里的初始化其实是对我们的edge；也就是初始化边的数据；如果我们设置了pre的前驱节点保存来后序找到这条最短源点路径的一路上的节点是哪些；以及dist数组初始化；因此还要对它也初始化：

定义的储存边的相关信息：

完成初始化：

for (int i = 0; i < m; i++) 
	//单向边和双向边适用：
cin >> edge_group[i]._u >> edge_group[i]._v >> edge_group[i]._w;

还有前驱节点的表也要初始化：

其次，就是dist源点距数组：

这里由于我们点的编号是从1开始（一般）；因此初始化的是1-n区间：

fill(dist+1, dist + n+1, maxi);//初始化dist要注意：我们从1-n的点的编号；也就是初始化这个区间（[迭代器)）

3.2对所有边进行松弛n-1次：

也就是我们遍历n-1遍对它的edge所有边进行松弛；发现有可以借助u到达v的就更新dist[v]：

for (int i = 1; i <= n - 1; i++) {

	//全边松弛操作：
	for (auto a : edge_group) {
		/只要存在负边权就需要特判：
		if (dist[a._u] != maxi&&dist[a._u] + a._w < dist[a._v]) {
			//这里一定要提前特判是否源点可以到达u这个位置；正数权无所谓；但是如果出现负数；很有可能源点无法到达
			//u，它就会加上uv的权（负数）;那么有可能导致就小于distv了；这就会更新；此时就出现了错误。
			pre[a._v] = a._u;//保存前驱
			dist[a._v] = dist[a._u] + a._w;
		
		}
	}

3.3退出小优化：

松弛操作对应位置check检查：

for (int i = 1; i <= n - 1; i++) {
	bool ck = 0;//如果少于n-1对全边进行松弛就完成了最短路径确定就可以提前return就好
	//全边松弛操作：
	for (auto a : edge_group) {
		/只要存在负边权就需要特判：
		if (dist[a._u] != maxi&&dist[a._u] + a._w < dist[a._v]) {
			//这里一定要提前特判是否源点可以到达u这个位置；正数权无所谓；但是如果出现负数；很有可能源点无法到达
			//u，它就会加上uv的权（负数）;那么有可能导致就小于distv了；这就会更新；此时就出现了错误。
			pre[a._v] = a._u;//保存前驱
			dist[a._v] = dist[a._u] + a._w;
			ck = 1;
		}
	}

3.4检查负环：

for (auto a : edge_group)//判断是否存在负环；如果存在那么不存在最短路径也就是说
	//；n-1次全边松弛无法达到最短路径;即对全边继续进行松弛还能更新dist就是存在负环
	if (dist[a._u] != maxi && dist[a._u] + a._w < dist[a._v]) return 0;

四.代码实现：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int maxi = 0x3f3f3f3f;
const int N = 1e6 + 1;
int dist[N], n, m;
int pre[N];//前驱节点
class edge {//储存边相关信息
public: edge(int u,int v,int w) :_u(u),_v(v),_w(w) {}
	int _u,  _v,  _w;//此边的初始点，终止点，边权。
private:

};
vector<edge>edge_group;//先定义edge再搞数组防止找不到;还未初始化

bool Bellman_Ford(int s,int n) {//n个点
	fill(dist+1, dist + n+1, maxi);//初始化dist要注意：我们从1-n的点的编号；也就是初始化这个区间（[迭代器)）
	dist[s] = 0;
	for (int i = 1; i <= n - 1; i++) {
		bool ck = 0;//如果少于n-1对全边进行松弛就完成了最短路径确定就可以提前return就好
		//全边松弛操作：
		for (auto a : edge_group) {
			/只要存在负边权就需要特判：
			if (dist[a._u] != maxi&&dist[a._u] + a._w < dist[a._v]) {
				//这里一定要提前特判是否源点可以到达u这个位置；正数权无所谓；但是如果出现负数；很有可能源点无法到达
				//u，它就会加上uv的权（负数）;那么有可能导致就小于distv了；这就会更新；此时就出现了错误。
				pre[a._v] = a._u;//保存前驱
				dist[a._v] = dist[a._u] + a._w;
				ck = 1;
			}
		}
		if (!ck) return 1;//进行判断是否可提前返回
	}
	for (auto a : edge_group)//判断是否存在负环；如果存在那么不存在最短路径也就是说
		//；n-1次全边松弛无法达到最短路径;即对全边继续进行松弛还能更新dist就是存在负环
		if (dist[a._u] != maxi && dist[a._u] + a._w < dist[a._v]) return 0;

	return 1;//正好n-1次松弛返回

}

void init_pre() {

	for (int i = 1; i <= n; i++)pre[i] = i;
}
int getpath(int x) {
	pre[x] == x ? x : getpath(pre[x]);
	cout << x << " ";
	return x;
}


int main() {
	cin >> n >> m;
	edge_group = vector<edge>(m,edge(0,0,0));//完成匿名初始化
	//edge_group.resize(m,edge(0,0,0));
	//绑定边的先关信息：
	for (int i = 0; i < m; i++) 
		//单向边和双向边适用：
	cin >> edge_group[i]._u >> edge_group[i]._v >> edge_group[i]._w;

	init_pre();


   // 调用 Bellman-Ford 算法
bool flag = Bellman_Ford(1, n);
if (flag) {
    if (dist[n] == maxi) cout << "unconnected" << endl;
	else {
		cout << dist[n] << endl;
		cout << "最短路径：" << endl;
		getpath(n);
	}
}
else {
    cout << "exist negative circle " << endl;
}
return 0;

}

五.例题应用及测试：

下面以一道含负权的为例：

题目传送门： 94. 城市间货物运输 I

解答代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int maxi = 0x3f3f3f3f;
const int N = 1e6 + 1;
int dist[N], n, m;
int pre[N];//前驱节点
class edge {//储存边相关信息
public: edge(int u,int v,int w) :_u(u),_v(v),_w(w) {}
	int _u,  _v,  _w;//此边的初始点，终止点，边权。
private:

};
vector<edge>edge_group;//先定义edge再搞数组防止找不到;还未初始化

bool Bellman_Ford(int s,int n) {//n个点
	fill(dist+1, dist + n+1, maxi);//初始化dist要注意：我们从1-n的点的编号；也就是初始化这个区间（[迭代器)）
	dist[s] = 0;
	for (int i = 1; i <= n - 1; i++) {
		bool ck = 0;//如果少于n-1对全边进行松弛就完成了最短路径确定就可以提前return就好
		//全边松弛操作：
		for (auto a : edge_group) {
			/只要存在负边权就需要特判：
			if (dist[a._u] != maxi&&dist[a._u] + a._w < dist[a._v]) {
				//这里一定要提前特判是否源点可以到达u这个位置；正数权无所谓；但是如果出现负数；很有可能源点无法到达
				//u，它就会加上uv的权（负数）;那么有可能导致就小于distv了；这就会更新；此时就出现了错误。
				pre[a._v] = a._u;//保存前驱
				dist[a._v] = dist[a._u] + a._w;
				ck = 1;
			}
		}
		if (!ck) return 1;//进行判断是否可提前返回
	}
	for (auto a : edge_group)//判断是否存在负环；如果存在那么不存在最短路径也就是说
		//；n-1次全边松弛无法达到最短路径;即对全边继续进行松弛还能更新dist就是存在负环
		if (dist[a._u] != maxi && dist[a._u] + a._w < dist[a._v]) return 0;

	return 1;//正好n-1次松弛返回

}

void init_pre() {

	for (int i = 1; i <= n; i++)pre[i] = i;
}
int getpath(int x) {
	pre[x] == x ? x : getpath(pre[x]);
	cout << x << " ";
	return x;
}


int main() {
	cin >> n >> m;
	edge_group = vector<edge>(m,edge(0,0,0));//完成匿名初始化
	//edge_group.resize(m,edge(0,0,0));
	//绑定边的先关信息：
	for (int i = 0; i < m; i++) 
		//单向边和双向边适用：
	cin >> edge_group[i]._u >> edge_group[i]._v >> edge_group[i]._w;

	init_pre();


   // 调用 Bellman-Ford 算法
bool flag = Bellman_Ford(1, n);
if (flag) {
    if (dist[n] == maxi) cout << "unconnected" << endl;
	else {
		cout << dist[n] << endl;
		//cout << "最短路径：" << endl;
		//getpath(n);
	}
}
else {
    cout << "exist negative circle " << endl;
}
return 0;

}

成功AC：

来测试一下我们的路径是不是1 2 5 6吧：

来测试一下上面的模拟例子：

到达3的最短路径：

到达2的最短路径：

ok,也是没有问题的。

最后再判断一下是否存在负环：

还是可以跑完成的。

六·小细节及疑点剖析：

我们肯定在设计的过程会发现有一些疑问；下面博主总结了四个小疑问点；来解析一下：

6.1为什么进行n-1次全变松弛后就完成了最短源点距的更新：

6.1.2从图的路径结构角度分析：

1`在一个有 n 个顶点的带权有向图中，如果存在从源点 s 到顶点 v 的最短路径，那么这条路径最多包含 n - 1 条边。因为如果路径包含了 n 条或更多边，那么必然会有一个顶点在路径中出现至少两次，即存在环。 2`如果这个环的权值之和为非负，那么去掉这个环后得到的路径会更短，所以最短路径中不会包含权值非负的环；如果环的权值之和为负，那么就不存在最短路径，因为可以无限次绕这个负权环来使路径长度无限小。 3`因此，在不存在负权环的情况下，从源点到任意顶点的最短路径长度最长为 n - 1 条边，这就决定了算法最多需要 n - 1 次松弛操作来确定所有顶点的最短距离。

6.1.3从算法迭代过程分析：

1`第一次迭代，算法可以确定从源点 s 经过 1 条边能到达的顶点的最短距离，即找到了源点 s 到其直接邻居顶点的最短距离。 2`第二次迭代，算法会考虑从源点 s 经过 2 条边能到达的顶点，通过对第一次迭代得到的结果进行松弛操作，更新从源点 s 经过 2 条边到达的顶点的最短距离。 3`以此类推，第 k 次迭代可以确定从源点 s 经过最多 k 条边能到达的顶点的最短距离。 4`由于最短路径最长为 n - 1 条边，所以经过 n - 1 次迭代后，算法就可以确定从源点 s 到所有顶点的最短距离。

说白了就是：负环不考虑；正环可去掉（在获得最短路径的时候）；因此源点到达一个点获得最短路径的最长边一定是n-1；故我们如果我们进行一次全边松弛操作一定会得到这些点中；源点只需要走一条边就可达的点的dist完成填充；那么当再次全边松弛；此时就会借助上一次填的确定好的最短路径的点完成套用得到只需要两条边的点；依次类推到n-1次全边松弛；完成dist数组填充。

6.2为什么我们可以根据check数组提前完成对Bellman-Ford算法的调用：

因为我们最坏的情况是遍历完n-1遍对全边的松弛才会找到所有的源点距的最短路径；但是有时候可能不需要这么多次就可以完成dist数组的最终填充操作；因此我们会发现也就是剩下的遍历全边松弛操作只要无dist更新就说明完成了；可用check数组检查一下。

6.3为什么可以那样判断是否存在负环：

这就是我们Bellman-Ford算法和后序我们会讲的SPFA算法不同于其他最短路径算法的特处；它可以通过特性对负环（这一圈总和是负数的环）；下面我们简单说明一下：

负环，它不是没有最短路径嘛（只要遍历环这条路径就会无限小）！因此我们当进行我们理论推导出来的n-1次全边松弛后；如果它存在负环；即当我们再次进行松弛还会发现最短路径；利用这个特性来检查负环：

如图：

验证了上述结论；负环可以一直松弛下去，并更新dist；因此上述判断可以使用作为负环判断条件。

6.4 为什么更新dist还要判断u点能否到达：

有负权的图需要注意；全正权无需考虑：

这里一定要提前特判是否源点可以到达u这个位置；正数权无所谓；但是如果出现负数；很有可能源点无法到达u，它就会加上uv的权（负数）;那么有可能导致就小于distv了；这就会更新；此时就出现了错误。

比如：dsit[u]=无穷（源点不可达）;而dist[v]=接近无穷（源点可达）；而u-->v的权是负权假设为

-oo/2;这样就会更新dist[v]；进行了错误的操作；因此要提前判断。

七.时间空间复杂度分析：

7.1时间复杂度：

其中n代表点个数；m代表边条数。

初始化距离数组的时间复杂度为o(n) ，因为需要对每个顶点的距离进行初始化。
松弛操作需要进行n-1 次迭代，每次迭代都要遍历所有的边 m，所以松弛操作的时间复杂度为O(nm) 。
检查负权回路时，需要再次遍历所有的边，时间复杂度为O(m) 。
总体时间复杂度为 O(nm)，这使得 Bellman - Ford 算法在处理大规模图时效率较低，尤其是当边数和顶点数都很大时。

7.2空间复杂度：

算法需要存储边的信息，假设用数组或向量存储边，空间复杂度为O(m) 。
还需要存储每个顶点的最短距离估计值，空间复杂度为 O(n)。
总体空间复杂度为O(n+m) 。

八.算法优势与局限性:

8.1优势：

①能处理负权边：

这是 Bellman - Ford 算法的一个显著优势。许多其他最短路径算法，如 Dijkstra 算法，只能处理边权非负的图。而 Bellman - Ford 算法可以在存在负权边的情况下正确计算最短路径，只要图中不存在负权回路。

②检测负权回路：

算法不仅能计算最短路径，还能检测图中是否存在负权回路。这在一些实际应用中非常重要，例如在金融领域的套利问题中，负权回路可能代表着存在套利机会。

8.2局限性：

时间复杂度较高：如前所述，其时间复杂度为 O(nm)，在处理大规模图时，计算量会非常大，运行效率较低。相比之下，Dijkstra 算法在使用优先队列优化后，时间复杂度可以降低到 O((n+m)*logn)<->或者nlogn，在边权非负的情况下性能更优。
对稀疏图效率较低：在稀疏图（边数n远小于m的图）中，Bellman - Ford 算法的性能也不如一些针对稀疏图优化的算法。

九.应用场景：

交通网络规划：在城市交通网络中，可能存在一些单向道路或收费不同的路段（对应图中的边权），可以使用 Bellman - Ford 算法计算从一个地点（源点）到其他各个地点的最短路径，考虑到某些路段可能因为交通拥堵、施工等原因导致通行成本增加（负权边），该算法能够更全面地处理这种复杂情况。
通信网络优化：在通信网络中，信号传输可能会受到各种因素的影响，导致不同链路的传输延迟不同（边权）。通过 Bellman - Ford 算法可以找到从一个节点到其他节点的最短延迟路径，即使存在一些干扰因素导致某些链路延迟增加（负权边），也能准确计算出最优路径。
经济决策分析：在经济学中，例如在计算投资回报时，可能存在一些成本和收益的复杂关系，某些决策可能会导致成本增加（负权边），而通过 Bellman - Ford 算法可以分析出从初始状态（源点）到不同目标状态的最优决策路径，帮助决策者做出更合理的选择。