首页 / 算法 / 【算法日记】贝尔曼-福德算法
【算法日记】贝尔曼-福德算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法日记】贝尔曼-福德算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1182字,纯文字阅读大概需要2分钟。
内容图文
如上图使用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 6for node in graph: 7 distance[node] = float( ‘Inf‘ ) 8 parent[node] = None 9 distance[source] = 0 1011for i in range( len( graph ) - 1 ): 12for from_node in graph: 13for to_node in graph[from_node]: 14if 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 1718for from_node in graph: 19for to_node in graph[from_node]: 20if distance[to_node] > distance[from_node] + graph[from_node][to_node]: 21return None, None 2223return distance, parent 2425def 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‘ ) 34print distance 35print parent 3637if__name__ == ‘__main__‘: 38 test()
原文:http://www.cnblogs.com/zimuzimu/p/7163810.html
内容总结
以上是互联网集市为您收集整理的【算法日记】贝尔曼-福德算法全部内容,希望文章能够帮你解决【算法日记】贝尔曼-福德算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。