首页 > 编程语言 > 详细

Bellman-Ford算法

时间:2019-01-17 16:18:32      阅读:165      评论:0      收藏:0      [点我收藏+]

分类:
单源最短路径算法。

适用于:
稀疏图(侧重于对边的处理)。

优点:
可以求出存在负边权情况下的最短路径。

缺点:
无法解决存在负权回路的情况。

时间复杂度:
O(NE),N是顶点数,E是边数。(因为和边有关,所以不适于稠密图)

算法思想:
很简单。一开始认为起点是“标记点”(dis[1] = 0),每一次都枚举所有的边,必然会有一些边,连接着“未标记的点”和“已标记的点”。因此每次都能用所有的“已标记的点”去修改所有的“未标记的点”,每次循环也必然会有至少一个“未标记的点”变为“已标记的点”。算法实现:

 

初始化:dis[s] = 0; dis[v] = oo(v != s); pre[s] = 0;
 
(伪代码)
for(int i = 1; i <= n - 1; i++)
  for(int j = 1; j <= E; j++)  //注意要枚举所有边,不能枚举点
    if(dis[u] + w[j] < dis[v])  //u, v分别是这条边连接的两个点
      {
        dis[v] = dis[u] + w[j]
        pre[v] = u;
      }

 

Bellman-Ford算法

原文:https://www.cnblogs.com/DWVictor/p/10282803.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!