Bellman-Ford算法

Bellman-Ford算法适用于单源最短路径问题（即求源结点到所有其他顶点的最短路径），使用注意事项：

(1)可以有负权边，但不能有负环

(2)适用于所有类型的图

存储结构采用边结构体数组，n为顶点数，m为边数

struct edge {
    int a, b, w;
}graph[m];

若源结点为顶点s，dis[i]标示源结点s到顶点i的最短距离（初始化dis[s]为0，其他为0x3f3f3f3f），为了防止串连，每轮循环开始前用bak数组备份dis数组

int dis[n], bak[n];

对于有向图中的某条边（起点a，终点b，边权w），若满足dis[b] $\leqslant$ dis[a] + w，称该边满足三角形不等式。如果有向图所有边都满足三角形不等式，则dis数组就是所求最短路径

Bellman-Ford算法对每条边进行松弛操作，使其满足三角形不等式，算法流程如下：

(1)扫描所有边e，进行松弛操作（若dis[e.b] < bak[e.a] + e.w，则用bak[e.a] + e.w更新dis[e.b]）

(2)重复上述步骤n-1次（循环k次后，dis数组中存储经过不超过k条边的单源最短路径，n个顶点的路径最多n-1条边，循环n-1次即可）

for (int i = 0; i < k; i++) {
    memcpy(bak, dis, sizeof(bak));
    for (int j = 0; j < m; j ++ ) {
        auto e = graph[j];
        dis[e.b] = min(dis[e.b], bak[e.a] + e.w);
    }
}

算法结束时，dis[i]存储源结点s到顶点i的最短距离，dis[i] > 0x3f3f3f3f/2表明顶点i不可达（由于对图中所有边进行松弛操作并且有负权边，就算s和i不连通，dis[i]也可能被更新）

注解：Bellman-Ford算法循环k次后的dis数组存储经过不超过k条边的单源最短路径，如果要求经过不超过k条边的单源最短路径只能用Bellman-Ford算法

---