图论最短路径——Bellman-Ford Algorithm算法_贝尔曼福特算法

贝尔曼-福特算法：处理负权边的最短路径算法

在图论中，寻找最短路径是一个常见且重要的问题。对于这个问题，有许多算法可以解决，其中最著名的是 Dijkstra 算法。然而，当图中包含负权边时，Dijkstra 算法可能无法正确工作。这时，贝尔曼-福特（Bellman-Ford）算法就派上了用场。

贝尔曼-福特算法的基本原理

贝尔曼-福特算法可以在含有负权边的图中找到从单个源点到所有其他顶点的最短路径。这个算法的核心是反复“松弛”图中的所有边。所谓“松弛”，指的是更新当前找到的到各顶点的最短路径估计。

算法步骤

1. 初始化：将所有顶点的最短路径估计值初始化为无穷大，只有源点的最短路径估计值设置为0。

2. 边的松弛：对每条边进行松弛操作。如果当前顶点v到顶点u的最短路径估计加上从v到u的边的权重比当前顶点u的最短路径估计更小，那么就更新顶点u的最短路径估计。

3. 重复执行：上述步骤在所有边上重复进行 |V|-1 次，其中 |V| 是顶点的数量。

4. 检测负权环：最后，再次对所有边进行松弛操作，如果还能找到更短的路径，则说明图中存在负权环。

时间复杂度

贝尔曼-福特算法的时间复杂度为 O(VE)，其中 V 是顶点数，E 是边数。这比 Dijkstra 算法的时间复杂度高，但它能处理更复杂的情况。

负权环检测

贝尔曼-福特算法的一个重要特性是能够检测图中是否存在负权回路。如果在完成标准的 |V|-1 次迭代后，再进行一次所有边的遍历，如果这时还能找到更短的路径，则说明图中存在负权回路。

代码实现

边的定义

struct Edge {
	int to;
	int weight;
 
	Edge(int t, int w) :to(t), weight(w) {}
};

用邻接表初始化一个图

	int n = 5;//顶点数
	vector<vector<Edge>>graph(n);
	graph[0].push_back(Edge(1, 10));
	graph[0].push_back(Edge(2, 5));
	graph[1].push_back(Edge(2, 2));
	graph[1].push_back(Edge(3, 1));
	graph[2].push_back(Edge(1, 3));
	graph[2].push_back(Edge(3, 9));
	graph[2].push_back(Edge(4, 2));
	graph[3].push_back(Edge(4, 4));
	graph[4].push_back(Edge(3, 6));
	graph[4].push_back(Edge(0, 7));

bellman算法实现

//graph是用邻接表表示的图
vector<int> bellman(const vector<vector<Edge>>& graph, const int& src) {
	int n = graph.size();
	//dis储存从出发节点到目标节点的最短距离，初始化为极大值
	vector<int> dis(n, INT_MAX);
	//出发节点到自身的距离为0
	dis[src] = 0;
 
	// 进行 n-1 次循环，如果某次循环时dis数组没有被更新则结束循环
	for (int k = 0; k < n - 1; k++) {
		//对每一个节点进行遍历
		for (int i = 0; i < n; i++) {
			//遍历每个节点的每条边
			for (const Edge& edge : graph[i]) {
				int u = i;
				int v = edge.to;
				int w = edge.weight;
				// 如果找到更短的路径则更新
				if (dis[u] < INT_MAX && dis[u] + w < dis[v]) {
					dis[v] = dis[u] + w;
				}
			}
		}
	}
 
	// 检测负权回路，更新dis数组时对图遍历了n-1次，如果第n次遍历仍然能找到更短的路径则说明图中存在负权回路
	for (int i = 0; i < n; i++) {
		for (const Edge& edge : graph[i]) {
			int u = i;
			int v = edge.to;
			int w = edge.weight;
			// 如果仍能找到更短的路径，说明存在负权回路
			if (dis[u] < INT_MAX && dis[u] + w < dis[v]) {
				cout << "图中存在负权回路" << endl;
				return vector<int>(); // 或者可以返回一个特殊值表示存在负权回路
			}
		}
	}
 
	return dis;
}

与Dijkstra算法的比较

#include <iostream>
#include <vector>
#include<queue>
 
using namespace std;
 
struct Edge {
	int to;
	int weight;
 
	Edge(int t, int w) :to(t), weight(w) {}
};
 
//graph是用邻接表表示的图
vector<int>dijkstra(const vector<vector<Edge>>& graph, int src) {
	int n = graph.size();
	//容器定义
		//储存各个顶点到src顶点的距离
	vector<int>dis(n, INT_MAX);
	//记录访问过的顶点	
	vector<bool>vis(n, false);
	//用优先级队列来处理距离最短的顶点，pair<int,int>的第一个int存储距离，第二个int存储顶点；底层用vector来存储这个队列；greater表示从小到大排
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
 
	//src顶点到自己的距离为0
	dis[src] = 0;
	pq.push({ 0,src });
 
	while (!pq.empty()) {
		//v表示当前距离最短的顶点
		int v = pq.top().second; pq.pop();
		//若是访问过当前顶点则跳过
		if (vis[v])continue;
		vis[v] = true;
		//访问邻接顶点
		for (const auto& edge : graph[v]) {
			int t = edge.to;
			int w = edge.weight;
 
			if (!vis[t] && w + dis[v] < dis[t]) {
				dis[t] = w + dis[v];
				pq.push({ dis[t],t });
			}
		}
 
	}
	return dis;
}
//graph是用邻接表表示的图
vector<int> bellman(const vector<vector<Edge>>& graph, const int& src) {
	int n = graph.size();
	//dis储存从出发节点到目标节点的最短距离，初始化为极大值
	vector<int> dis(n, INT_MAX);
	//出发节点到自身的距离为0
	dis[src] = 0;
 
	// 进行 n-1 次循环，如果某次循环时dis数组没有被更新则结束循环
	for (int k = 0; k < n - 1; k++) {
		//对每一个节点进行遍历
		for (int i = 0; i < n; i++) {
			//遍历每个节点的每条边
			for (const Edge& edge : graph[i]) {
				int u = i;
				int v = edge.to;
				int w = edge.weight;
				// 如果找到更短的路径则更新
				if (dis[u] < INT_MAX && dis[u] + w < dis[v]) {
					dis[v] = dis[u] + w;
				}
			}
		}
	}
 
	// 检测负权回路，更新dis数组时对图遍历了n-1次，如果第n次遍历仍然能找到更短的路径则说明图中存在负权回路
	for (int i = 0; i < n; i++) {
		for (const Edge& edge : graph[i]) {
			int u = i;
			int v = edge.to;
			int w = edge.weight;
			// 如果仍能找到更短的路径，说明存在负权回路
			if (dis[u] < INT_MAX && dis[u] + w < dis[v]) {
				cout << "图中存在负权回路" << endl;
				return vector<int>(); // 或者可以返回一个特殊值表示存在负权回路
			}
		}
	}
 
	return dis;
}
 
 
int main() {
	int n = 5;//顶点数
	vector<vector<Edge>>graph(n);
	graph[0].push_back(Edge(1, 10));
	graph[0].push_back(Edge(2, 5));
	graph[1].push_back(Edge(2, 2));
	graph[1].push_back(Edge(3, 1));
	graph[2].push_back(Edge(1, 3));
	graph[2].push_back(Edge(3, 9));
	graph[2].push_back(Edge(4, 2));
	graph[3].push_back(Edge(4, 4));
	graph[4].push_back(Edge(3, 6));
	graph[4].push_back(Edge(0, 7));
 
	vector<int>shortest_path = dijkstra(graph, 0);
	vector<int>sp = bellman(graph, 0);
	cout << shortest_path[3] << endl;//输出9
	cout << sp[3] << endl;//输出9
	return 0;
}

 这个图中不存在负权路径，不能体现bellman算法的优势

对于这种带负权的图dijkstra算法就失效了

适用场景

由于其能够处理负权边的特性，贝尔曼-福特算法非常适合于需要处理复杂权重系统的场景，如经济系统、交通网络等领域的建模。

结语

尽管贝尔曼-福特算法在时间复杂度上不如某些其他算法，但其能力处理更为复杂的图形结构，特别是含有负权边的图，使其成为一个非常有用的工具。