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基础教程