如何用Python编写贝尔曼-福特算法？
贝尔曼-福特算法（Bellman-Ford Algorithm）是一种解决带有负权边的单源最短路径问题的算法。本文将介绍如何使用Python编写贝尔曼-福特算法，并提供具体代码示例。
贝尔曼-福特算法的核心思想是通过逐步迭代来优化路径，直到找到最短路径为止。算法的步骤如下：
- 创建一个数组dist[]，存储从源点到其他顶点的最短距离。
- 将dist[]数组的所有元素初始化为无穷大，但源点的距离为0。
- 通过n-1次迭代，对于每条边(u, v)：
1) 如果dist[v] > dist[u] + weight(u, v)，则更新dist[v]为dist[u] + weight(u, v)。 - 检查是否存在负权环。对于每条边(u, v)：
1) 如果dist[v] > dist[u] + weight(u, v)，则存在负权环，无法确定最短路径。 - 如果不存在负权环，则最短路径已经被计算出来，dist[]数组即为最短路径。
以下是用Python编写的贝尔曼-福特算法的代码示例：
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def bellman_ford(self, src):
dist = [float("Inf")] * self.V
dist[src] = 0
for _ in range(self.V - 1):
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
print("图中存在负权环，无法确定最短路径")
return
self.print_solution(dist)
def print_solution(self, dist):
print("顶点 最短距离")
for i in range(self.V):
print(i, " ", dist[i])
# 示例用法
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)登录后复制
以上示例中，创建了一个图g，并添加了一些边。接着调用bellman_ford方法来计算最短路径并打印结果。在这个示例中，源点是0，最短路径将被计算出来。
贝尔曼-福特算法的时间复杂度为O(V*E)，其中V是顶点数，E是边数。在实际应用中，如果图中存在负权环，算法将不会停止，而会进入无限循环。因此，在使用贝尔曼-福特算法时，应先检查是否存在负权环。