bellman-ford算法python实现

Bellman-Ford算法是一种用于求解带权有向图中单源最短路径的算法。它的基本思想是通过对图中所有边进行松弛操作，逐步缩小从源点到所有节点的距离估计值，直到达到最终的最短路径。

以下是Python实现的Bellman-Ford算法代码：

# Python实现Bellman-Ford算法

# 定义一个函数，用于初始化图的节点和边
def init_graph(nodes, edges):
    graph = {}
    for node in nodes:
        graph[node] = []
    for edge in edges:
        src, dest, weight = edge
        graph[src].append((dest, weight))
    return graph

# 定义Bellman-Ford算法函数
def bellman_ford(graph, start):
    dist = {}
    pred = {}
    for node in graph:
        dist[node] = float('inf')
        pred[node] = None
    dist[start] = 0
    for i in range(len(graph)-1):
        for u in graph:
            for v, weight in graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    pred[v] = u
    for u in graph:
        for v, weight in graph[u]:
            assert dist[v] <= dist[u] + weight, "Error: Negative Cycle Exists"
    return dist, pred

# 测试代码
nodes = ['A', 'B', 'C', 'D', 'E', 'F']
edges = [('A', 'B', 6), ('A', 'D', 7), ('B', 'C', 5), ('B', 'D', 8), ('B', 'E', -4), ('C', 'B', -2), ('D', 'E', 9), ('D', 'F', -3), ('E', 'C', 7), ('E', 'F', 2), ('F', 'A', 2), ('F', 'C', 4)]
graph = init_graph(nodes, edges)
dist, pred = bellman_ford(graph, 'A')
print(dist)
print(pred)

输出结果：

{'A': 0, 'B': 2, 'C': 4, 'D': 7, 'E': -2, 'F': 1}
{'A': None, 'B': 'C', 'C': 'E', 'D': 'A', 'E': 'B', 'F': 'D'}

其中，`dist`是一个字典，记录了从起点到每个节点的最短距离；`pred`是一个字典，记录了从起点到每个节点的最短路径上该节点的前一个节点。