python实现Bellman-Ford算法

Bellman-Ford算法是一种用于计算图中单源最短路径的算法，即从一个顶点到其他所有顶点的最短路径。下面是一个使用Python实现Bellman-Ford算法的示例代码：

class Edge:
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.edges = []

    def add_edge(self, source, destination, weight):
        edge = Edge(source, destination, weight)
        self.edges.append(edge)

    def bellman_ford(self, start_vertex):
        # 初始化距离数组
        distances = {v: float('inf') for v in self.vertices}
        distances[start_vertex] = 0

        # 迭代 |V| - 1 次进行松弛操作
        for _ in range(len(self.vertices) - 1):
            for edge in self.edges:
                u = edge.source
                v = edge.destination
                w = edge.weight
                if distances[u] != float('inf') and distances[u] + w < distances[v]:
                    distances[v] = distances[u] + w

        # 检查是否存在负权环
        for edge in self.edges:
            u = edge.source
            v = edge.destination
            w = edge.weight
            if distances[u] != float('inf') and distances[u] + w < distances[v]:
                return "Graph contains negative weight cycle"

        return distances

# 创建图
vertices = ['A', 'B', 'C', 'D', 'E']
graph = Graph(vertices)

graph.add_edge('A', 'B', 4)
graph.add_edge('A', 'C', 2)
graph.add_edge('B', 'D', 3)
graph.add_edge('C', 'B', 1)
graph.add_edge('C', 'D', 4)
graph.add_edge('D', 'E', 2)
graph.add_edge('E', 'A', 1)

# 执行Bellman-Ford算法
start_vertex = 'A'
result = graph.bellman_ford(start_vertex)

# 打印最短路径
for vertex, distance in result.items():
    print(f"Shortest distance from {start_vertex} to {vertex}: {distance}")

在上述代码中，我们首先定义了 `Edge` 类来表示图的边，包含源顶点、目标顶点和边的权重。然后，我们定义了 `Graph` 类来表示图，包含顶点和边的列表，并实现了 `add_edge` 方法来添加边。

接下来，我们实现了 `bellman_ford` 方法来执行Bellman-Ford算法。该方法首先初始化距离数组为正无穷大，然后将起始顶点的距离设为0。接着，进行 `|V| - 1` 次迭代，每次迭代对所有边进行松弛操作。最后，我们再次遍历所有边，检查是否存在负权环。

最后，我们创建一个图，并添加边。然后，执行Bellman-Ford算法，并打印出起始顶点到各个顶点的最短路径。

希望这个示例能够帮助你理解如何在Python中实现Bellman-Ford算法！如果你还有其他问题，请随时提问。