1. 思路

1. 循环n次。
2. 每次遍历所有边。
3. 对每个终结点进行放缩。

2. 实现

1. 使用结构体存储所有边。
2. 初始化d[1] = 0 其他等于INF。
3. 进行算法主体实现。
4. 判断是否可以到达n d[N] > INF / 2。
5. 如果有边数的限制，需要使用backup数组进行放缩。

3.代码

int bellman_ford() {memset(d, 0x3f, sizeof(d));d[1] = 0;for (int i = 0; i < k; i++) {memcpy(backup, d, sizeof d);for (int j = 0; j < cnt; j++) {int u = edges[j].u, v = edges[j].v, w = edges[j].w; d[v] = min(d[v], backup[u] + w);// printf("v = %d d = %d\n", v, d[v]);}}if (d[n] > INF / 2) return INF;else return d[n];
}