C++基础算法10：Bellman_Ford

1、概念

Bellman-Ford（贝尔曼-福特）算法是一个用于单源最短路径问题的经典算法，能够处理带负权边的图，是图论中非常重要的算法之一。

2、实战例子

给定n个节点，m条边。可能存在重环，权重可能为负数。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1e5 + 10;
int n, m, k, d[N], me[N];  // d存储源点到节点的最短路径；me暂存当前的路径数组
struct Edge {int a, b, w;
} in[N];bool bell_ford() {fill(d, d + N, 0x3f3f3f3f);  // 初始化为无穷大d[1] = 0;  // 源点到自身距离为 0for (int i = 0; i < k; ++i) {memcpy(me, d, sizeof(d));  // 备份当前的最短路径for (int j = 0; j < m; ++j) {int a = in[j].a, b = in[j].b, w = in[j].w;d[b] = min(d[b], me[a] + w);  // 松弛操作}}return d[n] <= 0x3f3f3f3f / 2;  // 若目标节点距离大于无穷大，返回 false
}int main() {scanf("%d%d%d", &n, &m, &k);for (int i = 0; i < m; ++i) {scanf("%d%d%d", &in[i].a, &in[i].b, &in[i].w);}if (bell_ford()) cout << d[n];  // 输出最短路径else puts("impossible");  // 输出不可达return 0;
}

使用 me[] 是为了避免在一轮松弛中读取到“被修改后的值”，保证每次松弛都严格依赖上一次完整的结果，从而保证 Bellman-Ford 算法的正确性。

3、Dijkstra为什么解决不了负数权重的问题？

在Dijkstra算法中，每次都会选择一个当前最短的未处理节点，并且假设这个节点到达其他节点的路径不会再变得更短。该算法认为，当某个节点的最短路径确定后，后续不会有更短的路径通过该节点。这在所有边权都为非负数时是正确的，因为你只会逐步增加路径的长度，但不会出现路径长度突然减少的情况。