如何使用C++中的Bellman-Ford算法
Bellman-Ford算法是一种用于从单个源点到图中其他所有顶点求最短路径的算法。它可以处理包含负权边的图,因此被广泛应用于网络路由、金融市场分析等领域。本文将介绍如何使用C++中的Bellman-Ford算法,并提供代码示例。
Bellman-Ford算法核心思想是通过松弛操作(relaxation)不断更新估计的最短路径,直到达到最优解。它的时间复杂度为O(V * E),其中V是图中顶点的数量,E是边的数量。
下面是使用C++实现Bellman-Ford算法的示例代码:
#include <iostream>
#include <vector>
struct Edge {
int source;
int destination;
int weight;
};
void BellmanFord(std::vector<Edge>& edges, int numVertices, int source) {
std::vector<int> distance(numVertices, INT_MAX);
distance[source] = 0;
// Relaxation
for (int i = 1; i < numVertices; i++) {
for (const auto& edge : edges) {
int u = edge.source;
int v = edge.destination;
int w = edge.weight;
if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
distance[v] = distance[u] + w;
}
}
}
// Check for negative cycle
for (const auto& edge : edges) {
int u = edge.source;
int v = edge.destination;
int w = edge.weight;
if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
std::cout << "图中存在负权回路
";
return;
}
}
// 输出最短路径
for (int i = 0; i < numVertices; i++) {
if (distance[i] == INT_MAX) {
std::cout << "源点无法到达顶点 " << i << "
";
} else {
std::cout << "源点到顶点 " << i << " 的最短路径为: " << distance[i] << "
";
}
}
}
int main() {
std::vector<Edge> graph = {
{0, 1, -1},
{0, 2, 4},
{1, 2, 3},
{1, 3, 2},
{1, 4, 2},
{3, 2, 5},
{3, 1, 1},
{4, 3, -3}
};
int numVertices = 5;
int source = 0;
BellmanFord(graph, numVertices, source);
return 0;
}
在上述代码中,我们定义了一个边(Edge)结构体,包含边的起始点(source)、终止点(destination)和权重(weight)。
BellmanFord函数接收边的列表、图中顶点的数量和源点作为参数。它首先初始化距离数组distance,将源点的距离设为0,其他顶点的距离设为无穷大。
接着进行V-1轮松弛操作,每次遍历边集合并尝试更新最短路径。如果通过某条边松弛操作可获得更短的路径,则更新目标顶点的距离。这样就可以找到源点到其他顶点的最短路径。
最后,我们再次遍历所有边,检查是否存在负权回路。如果某条边在松弛操作后仍然能够更新目标顶点的距离,说明图中存在负权回路。
代码的最后输出最短路径。如果某个顶点的距离仍然是无穷大,说明源点无法到达该顶点;否则,输出源点到该顶点的最短路径。