[Python3]Bellman-Ford的实现及Yen式优化

原理分析见本人Github：

https://github.com/youhengchan/Yen-Bellman-Ford/blob/master/group2_ppt_yen.pdf

测试数据：

原始算法：

伪代码：

实现：

import timegraph_size = 10
counter = 0class Edge:def __init__(self, u, v, w):self.u = uself.v = vself.w = wdef recursive_print(dis, pre):global graph_sizedef print_helper(index, destination):if pre[index] == index:print("Route : {} -> ".format(index), end="")returnprint_helper(pre[index], destination)if index == destination:print("{} Distance = {}".format(destination, dis[destination]), end="")else:print("{} -> ".format(index), end="")for i in range(graph_size):if pre[i] == i:print("Route : {} Distance = 0".format(i), end="")else:print_helper(i, i)print("")def bellman_ford(edges, source):global graph_size, counterbegin = time.perf_counter()dis = []  # distance from source to the nodepre = []  # predecessor of nodeerror = Falsefor i in range(graph_size):dis.append(float('inf'))pre.append(i)dis[source] = 0# Initialize the graphfor i in range(graph_size - 1):   # |V| - 1 timescounter += 1# change = Falsefor edge in edges:if dis[edge.u] != float("inf") and dis[edge.v] > (dis[edge.u] + edge.w):dis[edge.v] = dis[edge.u] + edge.wpre[edge.v] = edge.u# change = True# if not change:#     break# check for the negative-weight cyclefor edge in edges:if (dis[edge.u] + edge.w) < dis[edge.v]:print("dis[{}] ({}) < dis[{}] ({}) + {}".format(edge.u, dis[edge.u], edge.v, dis[edge.v], edge.w))error = Trueend = time.perf_counter()return error, dis, pre, end-begindef main():global counteredges = []edges.append(Edge(0, 9, 9))edges.append(Edge(0, 2, 3))edges.append(Edge(0, 5, 5))edges.append(Edge(7, 9, 2))edges.append(Edge(7, 3, 0))edges.append(Edge(2, 7, 1))edges.append(Edge(9, 4, 3))edges.append(Edge(3, 4, 2))edges.append(Edge(3, 8, 1))edges.append(Edge(8, 2, 8))edges.append(Edge(8, 6, 2))edges.append(Edge(4, 8, -8))edges.append(Edge(6, 1, 0))edges.append(Edge(5, 1, 2))edges.append(Edge(1, 4, 9))err, dis, pre, time_consumption = bellman_ford(edges, 0)if err:print("Negative-weight cycle exist")else:print("Time consumption = ", time_consumption)recursive_print(dis, pre)print("Counter = ", counter)if __name__ == "__main__":main()

运行结果:

Yen氏优化：

伪代码：

实现：

import time
graph_size = 10
counter = 0class Edge:def __init__(self, u, v, w):self.u = uself.v = vself.w = wdef recursive_print(dis, pre):global graph_sizedef print_helper(index, destination):if pre[index] == index:print("Route : {} -> ".format(index), end="")returnprint_helper(pre[index], destination)if index == destination:print("{} Distance = {}".format(destination, dis[destination]), end="")else:print("{} -> ".format(index), end="")for i in range(graph_size):if pre[i] == i:print("Route : {} Distance = 0".format(i), end="")else:print_helper(i, i)print("")def yen_bellman_ford(edges, edge_plus, edge_minus, source):begin = time.perf_counter()global graph_size, counterdis = []  # distance from source to the nodepre = []  # predecessor of nodeerror = Falsefor i in range(graph_size):dis.append(float('inf'))pre.append(i)dis[source] = 0# Initialize the graphfor i in range(graph_size - 1):   # |V| - 1 timescounter += 1change = Falsefor edge in edge_plus:if dis[edge.u] != float("inf") and dis[edge.v] > (dis[edge.u] + edge.w):dis[edge.v] = dis[edge.u] + edge.wpre[edge.v] = edge.uchange = Truefor edge in edge_minus:if dis[edge.u] != float("inf") and dis[edge.v] > (dis[edge.u] + edge.w):dis[edge.v] = dis[edge.u] + edge.wpre[edge.v] = edge.uchange = Trueif not change:break# check for the negative-weight cyclefor edge in edges:if (dis[edge.u] + edge.w) < dis[edge.v]:print("dis[{}] ({}) < dis[{}] ({}) + {}".format(edge.u, dis[edge.u], edge.v, dis[edge.v], edge.w))error = Trueend = time.perf_counter()return error, dis, pre, end-begindef main():edges = []edge_plus = []edge_minus = []edge_plus.append(Edge(0, 2, 3))edge_plus.append(Edge(0, 5, 5))edge_plus.append(Edge(0, 9, 9))edge_plus.append(Edge(1, 4, 9))edge_plus.append(Edge(2, 7, 1))edge_plus.append(Edge(3, 4, 2))edge_plus.append(Edge(3, 8, 1))edge_plus.append(Edge(4, 5, 0))edge_plus.append(Edge(4, 8, -8))edge_plus.append(Edge(7, 9, 2))edge_minus.append(Edge(9, 4, 3))edge_minus.append(Edge(8, 6, 2))edge_minus.append(Edge(8, 2, 8))edge_minus.append(Edge(7, 3, 0))edge_minus.append(Edge(6, 1, 0))edge_minus.append(Edge(5, 1, 2))edges.extend(edge_minus)edges.extend(edge_plus)err, dis, pre, time_consumption = yen_bellman_ford(edges, edge_plus, edge_minus, 0)if err:print("Negative-weight cycle exist")else:print("Time consumption = ", time_consumption)recursive_print(dis, pre)print("Counter = ", counter)if __name__ == "__main__":main()

运行结果：