我们知道，狄克斯特拉算法可以用于寻找权值为正的有向无环图的最短路径。如果我们遇到图中某些边的权值为负，我们应该如何寻找最短路径呢?贝尔曼福德算法就是一种思路。
如果说狄克斯特拉算法是用一种“广度”的方式，每次寻找源点所能到达的距离最短的一个点，更新其邻居节点的距离（拓展）。那么贝尔曼福德算法就是用一种“深度”的方式，每次找到所有的路径，进行“松弛”操作（更新最短的路径）最终找到最短路径。
算法过程
松弛操作
贝尔曼福德算法是基于“松弛”操作来进行的，我们首先来看一下什么是松弛操作。其实表述起来也很简单，就是：
- 有两个点A、B都可以从源点经由某条路径到达，假设源点经由某条路径到A点的距离是M，源点经某条路径到达B点的距离是N；
- A点可直接到达B点，并且A点到B点的距离是L。
- 如果有 M(源点到A的距离) + L(A到B的距离) < N(源点到B的距离)，那么就说明有一条新的从源点到B的路线（途径A点）的距离要小于之前源点到B点的距离。此时我们更新源点到B的距离为 M + L。
这样下来，源点到B点的最小距离就被缩短了，也就是说我们找到了一条更近的能够从源点到达B点的路（经由A点）。这个路线的距离被缩短了，这个过程就是 “松弛” 的过程。
“松弛”过程.png
基于“深度”的松弛操作
对最短路径的一个认知
首先，我们要想清楚一件事，那就是：含有N个顶点的图，某两个顶点之间最短路径的深度不会超过N-1。
这句话的意思是，如果我们找到的是一条最短的路径，那么这条最短的路径包含的边肯定小于N-1条；最短路径最多边的情况就是经历了所有的节点，最终到达终点，此时路径的变数为N-1条。
为什么是这样呢？因为如果不是这样的话，那么图中肯定存在一个 环路：
存在环路的路径.png
我们看图，图中存在一条环路，B => C。如果我们从A出发最终到达D，那么我们的最短路径是什么呢？很容就能看到，最短路径是 A => B => D。如果我们经过一次B、C之间的环路，那么路径就会变为 A => B => C => B => D。此时路径长度就会增加B、C之间距离的2倍，就是2。也就是说，这种情况下，每每经过一次环路，路径的总长度就会增加2。
如果我们整个路径中没有环路，也就是没有两个点间互相到达的这种情况，那么我们的路径中，肯定就不会存在某个顶点重复出现的情况（刚才 A=>B=>C=>B=>D中存在环路，B就重复出现了），所以最多我们就是经历了所有的顶点：N个。这N个顶点可以确定N-1条边。所以：含有N个顶点的图，某两个顶点之间最短路径的深度不会超过N-1。
基于深度进行松弛操作
为什么说是基于深度进行的松弛操作呢？我们依然使用狄克斯特拉算法时候的路径图来证明这一点。另外，我们还需要两个图表（与狄克斯特拉算法的相同）：距离表、父节点表。
- 最初的时候，这个表中的值如下：
初始化的3个图表.png
我们得到了一张从Start开始，第一步只能到达A、B两点的初始化的距离表，也就是说，此时到达A、B的距离是已知的，因为可以由Start直接到达； 得到一个只有Start点作为父节点的两个点A、B的父地点表；还有一个全部路径的路径图。
- 我们遍历路径表中的 相邻两点之间的全部路径 一次，根据距离表更新每个点的到达距离。也就是对图进行一次松弛操作：
松弛操作.png
我们可以看到，初始化的时候，Start确定的是只能直接到达A、B两点。我们遍历所有的 两点之间 的路径（比如A、C之间的这条 A => C路径，起点为：A；终点为：C；权值为：2）。我们根据距离表，知道了起点到A的距离是5，到B的距离是3。由于A能到达C、D（存在路径：A => C 、A => D），所以，此时通过A到达C、D的距离就是（B点同理）：
对于经过A直接到达的点：
C的距离 = 5（Start到A的距离）+ 2（A到C的距离，也就是 A => C 的权值）= 7
D的距离 = 5（Start到A的距离）+ 2（A到C的距离，也就是 A => C 的权值）= 7
对于经过B直接到达的点：
C的距离 = 3 （Start到B的距离）+ 1（B到C的距离，也就是 B=> C 的权值）= 4
E的距离 = 3 （Start到B的距离）+ 6（B到E的距离，也就是 B=> C 的权值）= 9
我们依次遍历所有相邻两点之间的路径，遍历到 A => C 的时候，我们得到Start到C的距离是 5 + 2 = 7，将其写入距离表中；但是之后遍历到 B => C 的时候，我们又得到了Start到C的距离是 3 + 1 = 4 < 7，所以我们更改距离表，到达C的距离就更新为了4。遍历完所有路径后（松弛之后），我们更新了图中的距离表，就是现在这个样子。同样，我们将记录进距离表的点的相应的父节点也写进父地点表。
我们可以对比第一张图来看，此时我们做的操作，其实就是基于深度（浅色标线）的一次松弛操作。
- 继续2中的操作过程，我们再一次遍历全部的相邻两点之间的路径，我们可以得到如下三张图：
再次松弛.png
同样的操作，我们继续遍历所有相邻两点之间的路径（包括之前已经记录过距离的点，每次都遍历全部，因为不知道之前遍历过的会不会被再次更新，再次松弛）。所以这次我们松弛的边分别是（这个图来说之前两部遍历过后，有一些边再松弛权重已经不会改变）：
D => C、D => End，C => End、E => End
D => C : 查表得知到D的距离是7，D到C的距离是3，7 + 3 = 10 > 4（表中C的距离），所以C的距离不更新；
D => End: 查表知到D的距离是7，D到End的距离是4，7 + 4 = 11，表中无End，所以加入End = 11， 父地点为D；
C => End: 查表知到C的距离是4，C到End的距离是5，4 + 5 = 9 < 11（D=>End写入的），所以更新End的距离为 9， 父节点为C；
E => End: 查表知到E的距离是9， E到End的距离是1，9 + 1 = 10 > 9 (C => End更新过的)，所以不更新距离表和父节点表。
到此更新完毕了。我们得到了最终的距离表和父地点表。这样就得到了结论，从Start到到End的最小距离是9，路径是：End => C(End的父节点) => B(C的父节点) => Start(B的父节点) 的反转 Start => B => C => End。
这张图比较简单，我们只是初始化了一次各个表格，3次遍历(初始化算一次)所有的相邻节点之间的路径就得到了最终的路径。但是根据上面我们 对最短路径的一个认知 可以知道，并不是所有的节点分布都如此，但是，最短路径的深度最多就是 N(节点个数) - 1，所以我们最多需要遍历 N - 1 次。
算法可以用于含有负权值边的图
狄克斯特拉算法实际是依赖广度来进行拓展。依赖广度来进行拓展就会造成已经完成任务的顶点就不能再改变其距离，最终是通过累加的方式，算出所有顶点到达源点的最小路径，只能逐渐增加总权值，负值的存在会减小总权值，可能会造成某条路径上的顶点从原来的不是当前距离表中的最小值变成最小值。
由于贝尔曼福德算法是通过N-1次遍历，每次都遍历所有的两个相邻顶点之间的路径。所以是有穷次的单纯遍历去“松弛”，相当于在深度上去松弛，每次都会再次遍历所有的路径进行松弛，简单粗暴，所以路径上某个顶点距离的变化都是动态的来变化，因为每次遍历只在一个深度，并不能确定下一个深度遍历过后，某个顶点的到达距离是会变大还是缩小。所以不管放大还是缩小都是可以的，也就是不管路径的权值是正还是负都是可以的。
去除负权环
上面的过程实际上还没有结束，我们还需要思考一个问题：如果图中存在负权环会怎么样？答：存在负权环的话会使最终某几个顶点的到达距离值不收敛于一个小的值，每次更新都不断的减小，无限制的减小。
图中负权环的部分.png
如图，如果图中某一部分如图中所示，是一个包含有负权值的一个环路，那么我们第一次遍历所有相邻接点之间的路径进行松弛的时候，各个顶点的距离会发生变化（假设遍历顺序从 C => A 这条路径开始）：
遍历一次之后.png
我们可以看到，遍历一次之后，环中所有的顶点的距离值都变小了！如果图中的所有节点个数有N个，根据上面，我们会进行N-1次循环，那么在这N-1次循环中，这个环中的节点的距离每次都会减小，总的距离会无限减小，以至于最终找不到最短的路径（每次都减短，无限循环的话就无限减短，这肯定是不对的）。
所以我们要检查图中有没有负权环。检查的方法就是，在经历过之前N-1次循环之后，我们再次检查一遍所有的相邻节点之间的路径。如果不存在负权环，那么N-1次之后我们肯定找到了最短路径，那么我们此时图中的所有的相邻节点之间的路径都会满足（比如 C => A）：
C的距离 + C到A的距离 >= A的距离（如果C => A 是最短路径的一部分取=，如果不是就取 >）
如果存在负权环，导致的是这个环中所有的顶点的到达距离会无限减小。我们N-1次循环是有限的，但是N-1次循环之后，再次进行检查时（多加一次第N次循环），距离还是可以减小，也就是（比如C => A）:
C的距离 + C到A的距离 < A的距离（这个言外之意就是还能优化，我们知道经历N-1次循环之后已经找到最短路径了，这里还能再找，也就是无限减小最短路径的距离）
所以出现这种情况，我们就可以判定，这个图中存在负权环。如果存在负权环，那么我们经历N-1次循环之后我们得到的最短路径就不一定是最短的路径了。所以只有在经历过N-1次遍历松弛之后，再进行负权环的判定，如果没有负权环的存在，那么我们得到的最短路径，就是正确的。
算法实现
# -*- coding: utf-8 -*-
# @Time : 2019-01-02 12:27
# @Author : Jaedong
# @Version : 3.6
# @File : Bellman-Ford_algorithm.py
# @Software: PyCharm
# 定义一个表示边的类
class Edge:
u = '' # 边的起点
v = '' # 边的终点
weight = 0 # 边的权重
def __init__(self, u, v, weight):
self.u = u
self.v = v
self.weight = weight
# 贝尔曼福德算法的主体
def bellman_ford_algorithm(vertices, edges, start, end):
distances = {}
parents = {}
# 初始化参数
for v in vertices:
if v == start:
distances[v] = 0
else:
distances[v] = float('inf')
# 遍历并且松弛每一条边
for i in range(0, len(vertices) - 1):
for edge in edges:
if distances[edge.u] + edge.weight < distances[edge.v]:
distances[edge.v] = distances[edge.u] + edge.weight
parents[edge.v] = edge.u
# 检查是否有负权环
for edge in edges:
if distances[edge.u] + edge.weight < distances[edge.v]:
return None, None
# 更新了所有节点的到达最小距离，那么到达end的最小距离就是distances表中end所对应的值
distance = distances[end]
# 通过不断的回溯的方式，得到end到达start的路径，这样，就得到了start到达end的路径
parent = parents[end]
paths = [parent, end]
while parent is not start:
paths.insert(0, parents[parent])
parent = parents[parent]
return distance, paths
# 所有图中的顶点
vertex = ['Start', 'A', 'B', 'C', 'D', 'E', 'End']
# 所有图中的边
edges = [Edge('Start', 'A', 5), Edge('Start', 'B', 3),
Edge('A', 'C', 2), Edge('A', 'D', 2),
Edge('B', 'C', 1), Edge('B', 'E', 6),
Edge('C', 'End', 5),
Edge('D', 'C', 3), Edge('D', 'End', 4),
Edge('E', 'End', 1)]
distance, paths = bellman_ford_algorithm(vertex, edges, 'Start', 'End')
print('\n从 Start 到 End 的最短的距离是：{}, 路径是： {}'.format(distance, ' ==> '.join(paths)))
结果是：
找到最短路径.png
网友评论