说明
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基础教程
本文教程操作环境：windows7系统Python 3.9.1，DELL G3电脑。