bellman-ford算法和dijkstra算法的区别（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基础教程