Bellman-Ford-学习笔记

Bellman-Ford算法是一种图论中的算法，用于在带权图中找到单源最短路径，即从一个顶点到图中所有其他顶点的最短路径。与Dijkstra算法相比，Bellman-Ford算法的一个显著特点是它能够处理图中包含负权边的情况。

算法原理

Bellman-Ford算法通过对所有边的多次迭代来逐步减小从源点到所有点的估计距离，直到这些估计距离反映出真实的最短路径长度。算法的核心思想是动态规划。

算法步骤

1. 初始化：设置源顶点到自己的最短距离为 \(0\)，到其他所有顶点的最短距离为无穷大。
2. 松弛操作：对图中的所有边进行 \(V-1\) 次迭代（\(V\) 是顶点数），每次迭代中，更新图中所有边的两个顶点之间的最短距离。
3. 检测负权回路：在第V次迭代中检查是否还能更新最短距离，如果能，则图中存在负权回路。

C++实现

下面是Bellman-Ford算法的一个基本C++实现示例：

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct Edge {
	int src, dest, weight;
};
struct Graph {
	int V, E;
	vector<Edge> edges;
	Graph(int V, int E) {
		this->V = V;
		this->E = E;
	}
	void addEdge(int src, int dest, int weight) {
		edges.push_back({src, dest, weight});
	}
};
void BellmanFord(Graph& graph, int src) {
	int V = graph.V;
	int E = graph.E;
	vector<int> dist(V, numeric_limits<int>::max());
	dist[src] = 0;
	for (int i = 1; i <= V - 1; i++) {
		for (int j = 0; j < E; j++) {
			int u = graph.edges[j].src;
			int v = graph.edges[j].dest;
			int weight = graph.edges[j].weight;
			if (dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v])
				dist[v] = dist[u] + weight;
		}
	}
	for (int i = 0; i < E; i++) {
		int u = graph.edges[i].src;
		int v = graph.edges[i].dest;
		int weight = graph.edges[i].weight;
		if (dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v]) {
			cout << "Graph contains negative weight cycle" << endl;
			return;
		}
	}
	cout << "Vertex Distance from Source\n";
	for (int i = 0; i < V; ++i)
		cout << i << "\t\t" << dist[i] << endl;
}
int main() {
	int V = 5; // 顶点数
	int E = 8; // 边数
	Graph graph(V, E);
	// 添加边 src, dest, weight
	graph.addEdge(0, 1, -1);
	graph.addEdge(0, 2, 4);
	graph.addEdge(1, 2, 3);
	graph.addEdge(1, 3, 2);
	graph.addEdge(1, 4, 2);
	graph.addEdge(3, 2, 5);
	graph.addEdge(3, 1, 1);
	graph.addEdge(4, 3, -3);
	BellmanFord(graph, 0);
	return 0;
}

注意事项

• Bellman-Ford算法的时间复杂度为 \(O(VE)\)，对于稠密图可能不够高效。
• 算法能够检测图中是否存在负权重的环。如果在执行完所有松弛操作后，仍可以继续松弛，说明存在从源点可达的负权重环，因此无法找到最短路径。

扩展阅读

• 应用场景：Bellman-Ford算法不仅可以用来计算最短路径，还可以用来检测负权回路，这在某些应用中非常有用，比如在经济学或网络路由优化中。
• 算法优化：尽管标准的Bellman-Ford算法时间复杂度较高，但可以通过各种技巧进行优化，例如，如果一次遍历中没有任何更新，则可以提前终止算法。
• 与Dijkstra算法的比较：Dijkstra算法通常更快，但它不能处理负权边。因此，选择哪种算法取决于具体问题的需求。

结语

Bellman-Ford算法是解决带负权图中单源最短路径问题的一个强大工具。虽然它的时间复杂度比Dijkstra算法高，但它能够处理更广泛的问题，包括检测负权回路。理解并掌握Bellman-Ford算法，对于学习更高级的图论和网络路由算法非常有帮助。