Bellman-Ford算法

初步了解

Bellman-Ford算法是一种用于寻找带有负权边的图中的单源最短路径的算法。它可以处理一般的图，包括存在负权边和负权环的情况。

以下是Bellman-Ford算法的基本思想和步骤：

• 初始化：将源节点的距离设置为0，将所有其他节点的距离设置为无穷大（或一个很大的数）。

• 进行松弛操作：对图中的每条边进行一轮松弛操作。松弛操作是指通过检查是否存在一条更短路径来更新节点的距离值。

• 重复进行步骤2：重复进行|V|-1次松弛操作，其中|V|是图中节点的数量。这是为了确保所有可能的最短路径都被考虑到。

• 检测负权环：如果在进行第|V|-1次松弛操作后，仍然存在可以被进一步松弛的边，那么说明图中存在负权环。在这种情况下，Bellman-Ford算法无法得出正确的最短路径。

• 输出结果：如果不存在负权环，则最终的距离值就是源节点到每个节点的最短路径长度。

Bellman-Ford算法的时间复杂度为O(|V| * |E|)，其中|V|是节点数，|E|是边数。它可以处理负权边，但是在图中存在负权环的情况下，算法将无法收敛。

负权环是指在图中存在一个环路，其中环路上的边的权重之和为负值。换句话说，如果从起点沿着环路走一圈回到起点，所经过的边的权重之和是负数。
在最短路径算法中，负权环是一个问题，因为它会导致无限循环的情况。当存在负权环时，最短路径就没有意义，因为可以通过无限次地绕着负权环来获得更小的路径长度。
猜想一下，如果一个回路下来权值是一个负值，那么多绕几圈权值越来越小，这样就不存在最短路径

注意了解为什么经过|V| - 1 次操作后仍然可以被进一步松弛的边那么说明图中存在负权环？
在一个没有负权环的图中，最短路径的长度最多包含|V|-1条边。而当存在负权环时，路径可以无限地绕着负权环循环，从而使路径的长度无限减小。

正式了解

我们来看看代码实现

#include 
#include 
#include 

struct Edge {
    int source;
    int destination;
    int weight;
};

void BellmanFord(const std::vector<Edge>& edges, int numVertices, int source) {
    std::vector<int> distance(numVertices, std::numeric_limits<int>::max());
    std::vector<int> predecessor(numVertices, -1);
    distance[source] = 0;

    // 进行|V|-1次松弛操作
    for (int i = 1; i <= numVertices - 1; ++i) {
        for (const auto& edge : edges) {
            if (distance[edge.source] != std::numeric_limits<int>::max() &&
                distance[edge.source] + edge.weight < distance[edge.destination]) {
                distance[edge.destination] = distance[edge.source] + edge.weight;
                predecessor[edge.destination] = edge.source;
            }
        }
    }

    // 检测负权环
    for (const auto& edge : edges) {
        if (distance[edge.source] != std::numeric_limits<int>::max() &&
            distance[edge.source] + edge.weight < distance[edge.destination]) {
            std::cout << "图中存在负权环" << std::endl;
            return;
        }
    }

    // 输出最短路径
    std::cout << "节点\t距离\t路径" << std::endl;
    for (int i = 0; i < numVertices; ++i) {
        std::cout << i << "\t" << distance[i] << "\t";
        std::vector<int> path;
        int current = i;
        while (current != source) {
            path.push_back(current);
            current = predecessor[current];
        }
        path.push_back(source);
        for (int j = path.size() - 1; j >= 0; --j) {
            std::cout << path[j] << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    int numVertices = 5;
    std::vector<Edge> edges = {
        {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 source = 0;

    BellmanFord(edges, numVertices, source);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

代码还是比较好理解的

当实现 Bellman-Ford 算法时，我们的目标是计算从给定源节点到图中所有其他节点的最短路径。下面是代码实现的总体思路：

定义一个结构体 Edge 来表示图的边。它包含三个属性：源节点 source、目标节点 destination 和边的权重 weight。

BellmanFord 函数接受边的列表 edges、节点数量 numVertices 和源节点 source 作为输入参数。

初始化两个数组：distance 和 predecessor，分别用于存储从源节点到每个节点的距离和前驱节点。

将 distance 数组中除了源节点之外的所有元素初始化为无穷大，表示初始状态下到达这些节点的距离都是无穷大。将 predecessor 数组中所有元素初始化为 -1，表示初始状态下这些节点没有前驱节点。

进行 numVertices - 1 次松弛操作。每次循环遍历边的列表，对每条边进行松弛操作。如果发现从源节点出发经过当前边到达目标节点的路径比已知的最短路径更短，则更新 distance 数组和 predecessor 数组。

完成 numVertices - 1 次松弛操作后，检查是否存在负权环。遍历边的列表，再次进行一次松弛操作。如果发现存在从源节点出发经过当前边到达目标节点的路径比已知的最短路径更短，则说明图中存在负权环。

最后，输出最短路径的结果。遍历每个节点，打印节点的索引、从源节点到该节点的最短距离以及完整的最短路径。使用 predecessor 数组回溯每个节点的前驱节点，构建完整的路径。

这个实现思路遵循了 Bellman-Ford 算法的基本步骤，首先进行多次松弛操作以计算最短路径，然后检测负权环来判断是否存在无限缩小路径的可能性。最后，通过回溯前驱节点来构建最短路径。