Bellman-Ford – 小纸咚的blog

Bellman-Ford 算法是一种用于计算加权图中单源最短路径的算法。它可以处理边权为负的图，并且能够检测负权环（即从某个节点出发可以通过若干条边回到该节点并使得路径总权重为负的情况）。相比于 Dijkstra 算法，Bellman-Ford 算法的时间复杂度较高，但其适用范围更广。

算法原理

Bellman-Ford 算法的基本思想是通过松弛（Relaxation）操作逐步更新从源点到其他所有点的最短路径估计值。具体来说，算法的步骤如下：

初始化:
- 设置源点到自身的距离为 0。
- 设置源点到其他所有点的距离为正无穷（表示不可达）。
松弛操作:
- 对于图中的每一条边 (u, v)，如果从源点到 u 的距离加上边的权重小于从源点到 v 的当前距离，则更新 v 的距离。
- 这个过程需要重复进行 V-1 次，其中 V 是图中顶点的数量。因为在最坏的情况下，最短路径的长度最多为 V-1。
负权环检测:
- 在完成 V-1 次松弛操作后，进行一次额外的松弛操作。如果在这次操作中仍然能够更新任何节点的距离，则说明图中存在负权环。

算法步骤

初始化:

dist[source] = 0
dist[v] = ∞ for all v ≠ source

松弛每条边:

for i from 1 to V-1:
   for each edge (u, v) with weight w:
       if dist[u] + w < dist[v]:
           dist[v] = dist[u] + w

检查负权环:

for each edge (u, v) with weight w:
   if dist[u] + w < dist[v]:
       print("Graph contains a negative-weight cycle")

时间复杂度

Bellman-Ford 算法的时间复杂度为 (O(V \times E))，其中 (V) 是图中顶点的数量，(E) 是边的数量。这是因为需要对每一条边进行 (V-1) 次松弛操作。

代码实现

以下是 Bellman-Ford 算法的 C++ 实现：

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

struct Edge {
    int u, v, weight;
};

bool bellmanFord(int V, int E, vector<Edge>& edges, int source) {
    vector<int> dist(V, numeric_limits<int>::max()); // 初始化距离为无穷大
    dist[source] = 0; // 源点到自身的距离为0

    // 松弛每条边 V-1 次
    for (int i = 1; i < V; ++i) {
        for (const auto& edge : edges) {
            if (dist[edge.u] != numeric_limits<int>::max() && 
                dist[edge.u] + edge.weight < dist[edge.v]) {
                dist[edge.v] = dist[edge.u] + edge.weight;
            }
        }
    }

    // 检查负权环
    for (const auto& edge : edges) {
        if (dist[edge.u] != numeric_limits<int>::max() && 
            dist[edge.u] + edge.weight < dist[edge.v]) {
            cout << "Graph contains a negative-weight cycle" << endl;
            return false; // 存在负权环
        }
    }

    // 打印最短路径
    for (int i = 0; i < V; ++i) {
        if (dist[i] == numeric_limits<int>::max()) {
            cout << "Distance from source to vertex " << i << " is infinity" << endl;
        } else {
            cout << "Distance from source to vertex " << i << " is " << dist[i] << endl;
        }
    }

    return true; // 没有负权环
}

int main() {
    int V, E;
    cout << "Enter number of vertices and edges: ";
    cin >> V >> E;

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

    int source;
    cout << "Enter source vertex: ";
    cin >> source;

    bellmanFord(V, E, edges, source);

    return 0;
}

代码解析

数据结构:
- 使用 struct Edge 来表示边，包含起始点 u、终点 v 和权重 weight。
- 使用 vector<Edge> 来存储所有边。
初始化:
- 初始化距离数组 dist，源点的距离为 0，其余为无穷大。
松弛操作:
- 在循环中对每条边进行松弛操作，更新最短路径。
负权环检测:
- 进行一次额外的松弛操作来检测负权环。
输出结果:
- 打印每个顶点到源点的最短距离。

总结

Bellman-Ford 算法是一种有效的单源最短路径算法，特别适用于含有负权边的图。通过松弛操作和负权环检测，算法可以有效地找到最短路径并处理复杂的图结构。