前言
之前已经讲解了Dijkstra求最短路问题（点击查看），接下来讲解最短路问题中存在负权边的解法————Bellman - ford 算法。
老规矩，通过详细例题来带大家学习Bellman - ford 算法。
题目：有边数限制的最短路
题目链接：AcWing 853. 有边数限制的最短路
给定一个 n n n个点 m m m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n n n 号点的最多经过 k k k 条边的最短距离，如果无法从 1 号点走到 n n n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n , m , k n,m,k n,m,k。
接下来 $m $行，每行包含三个整数 x , y , z x,y,z x,y,z，表示存在一条从点 x x x 到点 y y y 的有向边，边长为 z z z。
点的编号为 1 ∼ n 1∼n 1∼n。
输出格式
输出一个整数，表示从 1 号点到 n n n 号点的最多经过 k k k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1 ≤ n , k ≤ 500 , 1≤n,k≤500, 1≤n,k≤500,
1 ≤ m ≤ 10000 , 1≤m≤10000, 1≤m≤10000,
1 ≤ x , y ≤ n ， 1≤x,y≤n， 1≤x,y≤n，
任意边长的绝对值不超过 10000 10000 10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
Bellman - ford 算法
Bellman-Ford算法是由理查德·贝尔曼（Richard Bellman）和莱斯特·福特（Lester Ford）创立的，用于求解单源最短路径问题的一种算法。该算法可以处理包含负权边的图，这是其他最短路径算法如Dijkstra算法无法处理的。
如下图所示，这就是最短路问题所应用到的所有算法，朴素Dijkstra算法和堆优化版的Dijkstra算法在之前就已经讲过，而对于存在负权边问题，Dijkstra就无法进行解决了（下面会举个例子来说明），只能用Bellman - ford算法和SPFA算法来解决。
为什么Dijkstra就无法解决负权边问题？ 如下图所示：
dijkstra算法在图中走出来的最短路径是1 -> 2 -> 4 -> 5，算出 1 号点到 5 号点的最短距离是2 + 2 + 1 = 5，然而还存在一条路径是1 -> 3 -> 4 -> 5，该路径的长度是5 + (-2) + 1 = 4，因此 dijkstra 算法失效。
什么是Bellman - ford 算法？
Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
(通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新)
Bellman - ford 算法步骤
Bellman-Ford算法通过多次松弛操作来逐步逼近最短路径。算法的基本步骤如下：
-
初始化：将源点到所有点的距离设为无穷大，源点到自身的距离设为0。（初始化操作很简单，构建邻接表进行初始化。）
-
松弛操作：对图中的每条边进行V-1次遍历（V是顶点数），每次遍历都尝试通过某条边更新源点到其他顶点的距离。如果通过某条边可以缩短距离，则进行更新。
加入每条边去松弛每个点到起点的距离（a到b的距离是w）
dist[b] = min(dist[b], last[a] + w)松弛操作需要last数组，用来存储在前一轮迭代（或称为“松弛操作”）中计算得到的从源节点到各个节点的最短距离，也就是备份。这是因为在Bellman-Ford算法中，我们需要对每一条边进行多次迭代（松弛操作），以尝试更新从源节点到图中所有其他节点的最短路径。
如果不加这个备份的话有可能会发生节点最短距离的串连；
比如说：
现在从3号结点走到4号节点要想进行松弛操作就必须先得到dist[3]，要想得到dist[3]就得知道dist[2]；
dist[2]=2，现在dist[3]是正无穷，用2号结点来更新3号结点，dist[3]=2+3=5;现在要更新dist[4]了，此时dist[4]=正无穷
出现问题了，dist[4]是用dist[3]是用正无穷来更新还是5呢
用dist[3]=5来更新那是下一次i迭代的事情；
这道题说是不经过k条边，说不定下一次就到k条边了，所以还是得用正无穷来更新的 -
检测负环：如果在V-1次遍历后仍然可以更新某些顶点的距离，则说明图中存在负环，无法找到最短路径。
详细代码与注释
n, m, k = map(int, input().split())# 初始化边的列表，用于存储图中的边，每条边由三个元素组成：(起点, 终点, 权重)
edge = []# 设置一个足够大的值N，用于表示图中节点的数量上限（这里假设最多有100010个节点）
N = 100010# 初始化距离数组dist，用于存储从源节点（假设为节点1）到每个节点的最短距离
# 初始时，除了源节点到自身的距离为0外，其他所有节点的距离都设置为正无穷大
dist = [float('inf')] * N
dist[1] = 0# 读取m条边，每条边由三个整数组成：起点a，终点b，权重c
for i in range(m):a, b, c = map(int, input().split())edge.append((a, b, c))# 定义Bellman-Ford算法的函数
def bellman_ford():# 对图中的每条边进行k次松弛操作，尝试更新从源节点到每个节点的最短距离for i in range(k):# 复制上一轮迭代后的距离数组，用于比较更新前后的距离last = dist.copy()# 遍历每一条边，尝试通过当前边更新终点b的距离for j in range(m):a, b, w = edge[j] # 当前边的起点a，终点b，权重w# 如果通过起点a到达b的距离比当前记录的b的距离更短，则更新b的距离dist[b] = min(dist[b], last[a] + w)# 检查是否存在从源节点到目标节点n的路径# 如果dist[n]仍然是正无穷大，则表示不存在这样的路径，返回'impossible'if dist[n] == float('inf'):return 'impossible'else:# 否则，返回从源节点到目标节点n的最短距离return dist[n]print(bellman_ford())
总结
Bellman - ford 算法的时间复杂度是 O ( n m ) O(nm) O(nm)，而对于负权边问题的最短路，还有一种更优的求解算法也就是SPFA算法，可以把时间复杂度降到 O ( m ) O(m) O(m)，下一篇博客我们来学习SPFA算法。