我们在之前的文章中已经讨论了最短路径算法中最经典的Dijkstra‘s Algorithm。然而，Dijkstra's Algorithm虽然好用，却仍然存在一些缺点即无法解决带有负权重路线的问题，改进后的Dijkstra算法尽管可以解决一些简单的负权重问题，但仍然无法解决带有负循环的图的最短路径问题。
为了弥补Dijkstra's Algorithm的缺点，我们需要借用一个适用于任何图的最短路径算法，那就是我们今天要介绍的贝尔曼-福德算法。
Dijkstra 算法是一种贪心算法，时间复杂度为 O((V+E)LogV)（使用优先序列改进后）。Dijkstra 不适用于具有负权重的图，Bellman-Ford 适用于此类图，同时Bellman-Ford 也比 Dijkstra 更容易实现，并且非常适合分布式系统，缺点是 Bellman-Ford 的时间复杂度是 O(V * E)。
使用 Bellman-Ford Algorithm 查找到所有顶点的最短距离的步骤：
- 首先，初始化从源点到所有顶点的距离为无穷，原点到原点本身的距离为 0，即创建大小为 |V| 的数组 dist[] 所有值都是无限的，除了 dist[src] ，其中 src 是源顶点。
- 然后，计算最短路径，下面的操作重复执行 |V|-1 次，这里 |V| 是给定图中的顶点数，每次对每个边缘 uv 执行以下操作
- 如果 dist[v] > dist[u] + 边 uv 的权重，则更新 dist[v] 为dist[v] = dist[u] + 边 uv 的权重
- 最后检查图中是否存在负权重循环。再次遍历每条边，对每条边uv执行以下操作：
- 如果dist[v] > dist[u] + 边uv的权重，那么“图包含负权重循环”
- 第三步的思路是，第二步求出最短路径（如果图表不包含负权重循环）。如果我们再次遍历所有边并发现任何顶点存在更短的路径，则证明存在负权重循环。
Bellman-Ford Algorithm 的原理
与其他动态规划问题一样，该算法以自下而上的方式计算最短路径。它首先计算路径中最多有一条边的最短距离。然后，它计算最多有 2 条边的最短路径，依此类推。在外循环的第 i 次迭代之后，计算最多具有 i 条边的最短路径。可以有最大值 |V| – 任何简单路径中的 1 条边，这就是外循环运行 |v| 的原因 – 1 次。这个想法是，假设如果我们计算了最多具有 i 个边的最短路径，则没有负权重循环，那么对所有边的迭代保证给出最多具有 (i+1) 个边的最短路径。
算法图解
第 1 步：设0为起点。将所有距离初始化为无穷，除了0到自身的距离。图中的顶点总数为 5，因此每条边都必须处理 4 次。
第二步：所有边按如下顺序处理：(B, E), (D, B), (B, D), (A, B), (A, C), (D, C), ( B, C), (E, D)。当第一次处理所有边时，我们得到以下距离。第一行显示初始距离。第二行显示处理边缘 (B, E)、(D, B)、(B, D) 和 (A, B) 时的距离。第三行显示处理（A，C）时的距离。第四行显示处理 (D, C)、(B, C) 和 (E, D)时的距离。
第 3 步：第一次迭代计算出了最短路径只包涵一条边的距离。第二次遍历所有边时，我们得到以下距离（最后一行显示最终值）。
第 4 步：第二次遍历保证给出最多 2 条边的所有最短路径。注意，第二次遍历后所有距离已经最小化，因此第三次和第四次遍历不会更新距离。
下面是Bellman-Ford算法的Python实现
class Graph:
def __init__(self, vertices):
self.V = vertices # No. of vertices
self.graph = []
# function to add an edge to graph
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
# utility function used to print the solution
def printArr(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("{0}\t\t{1}".format(i, dist[i]))
# The main function that finds shortest distances from src to
# all other vertices using Bellman-Ford algorithm. The function
# also detects negative weight cycle
def BellmanFord(self, src):
# Step 1: Initialize distances from src to all other vertices
# as INFINITE
dist = [float("Inf")] * self.V
dist[src] = 0
# Step 2: Relax all edges |V| - 1 times. A simple shortest
# path from src to any other vertex can have at-most |V| - 1
# edges
for _ in range(self.V - 1):
# Update dist value and parent index of the adjacent vertices of
# the picked vertex. Consider only those vertices which are still in
# queue
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Step 3: check for negative-weight cycles. The above step
# guarantees shortest distances if graph doesn't contain
# negative weight cycle. If we get a shorter path, then there
# is a cycle.
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
print("Graph contains negative weight cycle")
return
# print all distance
self.printArr(dist)
# Driver's code
if __name__ == '__main__':
g = Graph(5)
g.addEdge(0, 1, -1)
g.addEdge(0, 2, 4)
g.addEdge(1, 2, 3)
g.addEdge(1, 3, 2)
g.addEdge(1, 4, 2)
g.addEdge(3, 2, 5)
g.addEdge(3, 1, 1)
g.addEdge(4, 3, -3)
# function call
g.BellmanFord(0)
其他语言实现下载链接：
（包含各种语言：C、Python、Java、C++、C#、Javascript等均有示例）文章来源：https://www.toymoban.com/news/detail-478004.html
免费资源下载：Bellman-Ford Algorithm文章来源地址https://www.toymoban.com/news/detail-478004.html
到了这里，关于最短路径算法 | Bellman-Ford Algorithm的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
