bellman_ford.py 文件源码

def run_bellman_ford(test_num, num_nodes, make_graph_fn):
    print("\t\t~~~ Test: %s ~~~" % test_num)
    distance = [math.inf for _ in range(num_nodes)]
    parents = [-1 for _ in range(num_nodes)]
    graph, source, target, expected = make_graph_fn()
    no_neg_cycle = bellman_ford(graph, source, parents, distance)
    nodes = graph.get_vertices()
    distances_labeled = []
    for i in range(len(nodes)):
        distances_labeled.append((nodes[i].rep, distance[i]))
    print("Distances labeled: %s" % distances_labeled)
    print("Parents: %s" % parents)
    if no_neg_cycle:
        path = []
        current = target.index
        while current != -1:
            path.append(nodes[current].rep)
            current = parents[current]
        path = path[::-1]
        print("Shortest path from: %s to %s is \n%s" % (source.rep, target.rep, path))
    else:
      print("Has negative cycle, no solution.")
    print("Passed: %s\n" % (expected == distance if no_neg_cycle else no_neg_cycle == expected))

# -------------------------------------- driver functions ----------------------------------------