Python中如何实现Bellman-Ford算法？

def bellman_ford(graph, source):
    # 初始化距离数组，设为无穷大
    distance = {node: float('inf') for node in graph}
    distance[source] = 0

    # 放松|V|-1次
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor in graph[node]:
                if distance[node] + graph[node][neighbor] < distance[neighbor]:
                    distance[neighbor] = distance[node] + graph[node][neighbor]

    # 检查负权环
    for node in graph:
        for neighbor in graph[node]:
            if distance[node] + graph[node][neighbor] < distance[neighbor]:
                raise ValueError("Graph contains a negative-weight cycle")

    return distance

def bellman_ford_with_path(graph, source):
    distance = {node: float('inf') for node in graph}
    distance[source] = 0
    predecessor = {node: None for node in graph}

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor in graph[node]:
                if distance[node] + graph[node][neighbor] < distance[neighbor]:
                    distance[neighbor] = distance[node] + graph[node][neighbor]
                    predecessor[neighbor] = node

    for node in graph:
        for neighbor in graph[node]:
            if distance[node] + graph[node][neighbor] < distance[neighbor]:
                raise ValueError("Graph contains a negative-weight cycle")

    return distance, predecessor

def reconstruct_path(predecessor, start, end):
    path = []
    current = end
    while current != start:
        path.append(current)
        current = predecessor[current]
    path.append(start)
    return path[::-1]

# 使用示例
graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}

distance, predecessor = bellman_ford_with_path(graph, 'A')
print("最短距离:", distance)
print("前驱节点:", predecessor)

path = reconstruct_path(predecessor, 'A', 'E')
print("从A到E的最短路径:", path)