首页 > 代码库 > 【算法日记】贝尔曼-福德算法
【算法日记】贝尔曼-福德算法
如上图使用Dijkstra算法将无法获取到最短路径
1.A->C->D 5
2.A->B...没有
最近路径为5.但是实际上B->C的路径为-2. A->B->C->D的最短开销为3
Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权,在没有负权回路存在时(负权回路的含义是,回路的权值和为负。)即便有负权的边,也可以采用贝尔曼-福德算法算法正确求出最短路径。
算法实现
1 def bellman_ford( graph, source ): 2 3 distance = {} 4 parent = {} 5 6 for node in graph: 7 distance[node] = float( ‘Inf‘ ) 8 parent[node] = None 9 distance[source] = 0 10 11 for i in range( len( graph ) - 1 ): 12 for from_node in graph: 13 for to_node in graph[from_node]: 14 if distance[to_node] > graph[from_node][to_node] + distance[from_node]: 15 distance[to_node] = graph[from_node][to_node] + distance[from_node] 16 parent[to_node] = from_node 17 18 for from_node in graph: 19 for to_node in graph[from_node]: 20 if distance[to_node] > distance[from_node] + graph[from_node][to_node]: 21 return None, None 22 23 return distance, parent 24 25 def test(): 26 graph = { 27 ‘a‘: {‘b‘: -1, ‘c‘: 4}, 28 ‘b‘: {‘c‘: 3, ‘d‘: 2, ‘e‘: 2}, 29 ‘c‘: {}, 30 ‘d‘: {‘b‘: 1, ‘c‘: 5}, 31 ‘e‘: {‘d‘: -3} 32 } 33 distance, parent = bellman_ford( graph, ‘a‘ ) 34 print distance 35 print parent 36 37 if __name__ == ‘__main__‘: 38 test()
【算法日记】贝尔曼-福德算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。