一、(bellman-ford)算法
算法思路
for n次 //迭代n次（n个结点）
for 所有边 //a,b,w 表示存在一条a->b 的边，权重是 w
dist[b]=min(dist[b],dist[a]+w)
和迪杰斯特拉算法基本思想是一致的:通过一个一个的引入其它结点，让两点之间的距离更短。数学上可以证明，执行完(n)次后，最终可以得到(asim b)的最短路径。
二、要点总结
-
(bellman-ford)可以处理负权边,而(Dijkstra)只能处理正权边。
-
(bellman-ford)算法可以处理负权回路，因为它求得的最短路是有限制的，是限制了边数的，这样不会永久的走下去，会得到一个解；
-
有负权回路的话，最短路是不一定存在的。为什么是不一定，可以看图(1)和图(2).
-
(bellman-ford)是可以找负环的，但时间复杂度比较高，一般不用它来找负环。(bellman-ford)能干的事，(SPFA)都能干，而且时间复杂度比(bellman-ford)要低。
-
(SPFA)算法各方面优于该算法，但是在碰到限制了最短路径长度时就只能用(bellman-ford)了，此时直接把(n)重循环改成(k)次循环即可
-
有边数限制的最短路径
(bellman-ford)算法擅长解决有边数限制的最短路问题,其它算法没有这个功能！
比个现实中的场景：旅游(n)个城市，(1)->(n)没有直达的飞机，需要经其它的城市进行中转，票价就是中转的机票票价之和，每次中转都会让人的心情不爽一点，也就是不能超过(k)次中转。这个场景因为
限制了边数的数量上限(k)，就只能用(bellman-ford)算法。
三、C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 510; //结点数
const int M = 10010; //边数
//存边的方式
struct Edge {
//三个整数a，b，c，表示存在一条从点a到点b的有向边，边长为c。
int a, b, c;
} edges[M]; //边的数组
int n, m; //n个结点，m条边
int k; //表示从1号点到n号点的最多经过k条边的最短距离
int dist[N];//距离数组
int backup[N];//备份数组
// 输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离
void bellman_ford() {
// 初始化为无穷大
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; //1点节点到自己的长度是0
//循环k次，因为只有k次机会
for (int i = 1; i <= k; i++) {
//上一次的结果(备份出来)
//为了在一次迭代中防止更新多条边的情况，需要备份出来
memcpy(backup, dist, sizeof dist);//防止发生串联，只用上一次迭代的结果就不会发生串联。
//循环所有边
for (int j = 0; j < m; j++) {
Edge e = edges[j];
dist[e.b] = min(dist[e.b], backup[e.a] + e.c);
}
}
}
int main() {
//读入优化
ios::sync_with_stdio(false);
//读入数据
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
//三个整数a，b，c，表示存在一条从点a到点b的有向边，边长为c。
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
//调用bellman_Ford算法
bellman_ford();
//输出结果
if (dist[n] > INF / 2) puts("impossible");
else printf("%d
", dist[n]);
return 0;
}