说明

代码

def bellman_ford(src,graph):
    num = len(graph)
    dist = {node:float("Inf") for node in graph}
    dist[src] = 0
    for _ in range(num-1):
        for s in graph:
            for d,w in graph[s].items():
                if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                    dist[d] = dist[s] + w
    for s in graph:
            for d,w in graph[s].items():
                if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                    # 存在负权路径的环
                    print("存在负权路径的环")
                    return False
    #结果
    print(dist)
    return True

graph = { #图
    's':{'t':6,'y':7},
    't':{'y':8,'x':5,'z':-4},
    'y':{'x':-3,'z':9},
    'x':{'t':-2},
    'z':{'s':2,'x':7}
    } 
bellman_ford('s',graph)
# {'s': 0, 't': 4, 'y': 7, 'x': 6, 'z': 0}
graph = { 'A': {'B': -1, 'C': 4}, 'B': {'C': 3, 'D': 2, 'E': 2}, 'C': {}, 'D': {'B': 1, 'C': 5}, 'E': {'D': -3} }
bellman_ford('A',graph)
# {'A': 0, 'B': -1, 'C': 2, 'D': -2, 'E': 1}