python实现贝尔曼算法

贝尔曼-福德算法是一种用于查找图形中单源最短路径的算法。它可以处理具有负权重边的图形，并且可以检测到负权重环。下面是Python实现贝尔曼-福德算法的示例代码：

from collections import defaultdict

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 print_arr(self, dist):
        print("Vertex Distance from Source")
        for i in range(self.V):
            print("{0}\t\t{1}".format(i, dist[i]))

    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("Graph contains negative weight cycle")
                return

        self.print_arr(dist)

这个实现使用了一个Graph类来表示图形，其中包含一个add_edge方法来添加边，一个print_arr方法来打印最短路径，以及一个bellman_ford方法来实现贝尔曼-福德算法。在bellman_ford方法中，我们首先将所有距离初始化为无穷大，然后将源节点的距离设置为0。然后，我们进行V-1次迭代，其中V是节点数。在每次迭代中，我们遍历所有边，并更新距离，如果发现更短的路径，则更新距离。最后，我们再次遍历所有边，检查是否存在负权重环。如果存在，则打印出来。