Bellman-Ford算法_bellman-fold蒜贩-CSDN博客

本文链接：https://blog.csdn.net/illhm/article/details/146280955

Bellman-Ford算法是一种用于解决单源最短路径问题的算法，它可以在加权图中找到从一个源点到所有其他顶点的最短路径，即使图中包含负权边。与Dijkstra算法不同，Bellman-Ford算法能够处理负权边，并且可以检测图中是否存在负权环。

Bellman-Ford算法的基本思想

Bellman-Ford算法的核心思想是动态规划。它通过逐步松弛（relaxation）图中的所有边，逐步逼近最短路径的值。算法的基本步骤如下：

初始化：
- 将源点到自身的距离设为0，即 dist[source] = 0。
- 将源点到其他所有顶点的距离设为无穷大，即 dist[v] = +∞。
松弛操作：
- 对图中的每条边 (u, v)，尝试更新从源点到顶点 v 的距离：
```
if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)
```
- 这个操作称为松弛，目的是找到更短的路径。
重复松弛操作：
- 对所有边重复上述松弛操作 n-1 次（其中 n 是图中顶点的数量）。根据最短路径的性质，任何最短路径最多包含 n-1 条边，因此经过 n-1 次松弛后，所有最短路径的值都会被正确计算。
检测负权环：
- 再次遍历所有边，如果还能找到可以松弛的边（即 dist[u] + weight(u, v) < dist[v]），则说明图中存在负权环，无法找到最短路径。

Bellman-Ford算法的实现

以下是Bellman-Ford算法的标准实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

struct Edge {
    int u, v, weight; // 表示边 (u, v)，权重为 weight
};

bool bellmanFord(int n, int source, vector<Edge>& edges, vector<int>& dist) {
    // 初始化距离数组
    dist.assign(n + 1, INT_MAX); // 假设顶点编号从1开始
    dist[source] = 0; // 源点到自身的距离为0

    // 进行 n-1 次松弛操作
    for (int i = 1; i < n; i++) {
        bool updated = false; // 用于检测是否还有更新
        for (const auto& e : edges) {
            if (dist[e.u] != INT_MAX && dist[e.u] + e.weight < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.weight;
                updated = true;
            }
        }
        if (!updated) break; // 如果没有更新，提前终止
    }

    // 检测负权环
    for (const auto& e : edges) {
        if (dist[e.u] != INT_MAX && dist[e.u] + e.weight < dist[e.v]) {
            return false; // 存在负权环
        }
    }

    return true; // 不存在负权环
}

int main() {
    int n, m, source;
    cout << "Enter number of vertices and edges: ";
    cin >> n >> m;
    cout << "Enter source vertex: ";
    cin >> source;

    vector<Edge> edges;
    cout << "Enter edges (u, v, weight):" << endl;
    for (int i = 0; i < m; i++) {
        Edge e;
        cin >> e.u >> e.v >> e.weight;
        edges.push_back(e);
    }

    vector<int> dist;
    if (bellmanFord(n, source, edges, dist)) {
        cout << "Shortest distances from source vertex " << source << ":" << endl;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INT_MAX) {
                cout << "Vertex " << i << ": No path" << endl;
            } else {
                cout << "Vertex " << i << ": " << dist[i] << endl;
            }
        }
    } else {
        cout << "Graph contains a negative-weight cycle." << endl;
    }

    return 0;
}