python Bellman-Ford算法是什么
说明
1、Bellman-Ford算法是包含负权图的单源最短路径算法。
算法原理是对图进行V-1放松操作,获得所有可能的最短路径。
2、Bellman-Ford算法可以处理负面边缘。它的基本操作扩展是在深度上搜索,而放松操作是在广度上搜索。
它可以在不影响结果的情况下操作负面边缘。
Bellman-Ford算法效率低,时间复杂度高达o(V*E),v、e分别为顶点和边数。SPFA是Bellman-Ford的队列优化,通过维护队列可以大幅度减少重复计算,时间复杂度为o(k*E)。
实例
defbellman_ford(graph,source): distance={} parent={} fornodeingraph: distance[node]=float('Inf') parent[node]=None distance[source]=0 foriinrange(len(graph)-1): forfrom_nodeingraph: forto_nodeingraph[from_node]: ifdistance[to_node]>graph[from_node][to_node]+distance[from_node]: distance[to_node]=graph[from_node][to_node]+distance[from_node] parent[to_node]=from_node forfrom_nodeingraph: forto_nodeingraph[from_node]: ifdistance[to_node]>distance[from_node]+graph[from_node][to_node]: returnNone,None returndistance,parent deftest(): graph={ 'a':{'b':-1,'c':4}, 'b':{'c':3,'d':2,'e':2}, 'c':{}, 'd':{'b':1,'c':5}, 'e':{'d':-3} } distance,parent=bellman_ford(graph,'a') printdistance printparent if__name__=='__main__': test()
以上就是python Bellman-Ford算法的介绍,希望对大家有所帮助。更多python学习指路:python基础教程
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。