当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

bellman-ford(贝尔曼-福特)算法

发表于: 2009-01-21   作者:comsci   来源:转载   浏览:
摘要: Bellman-Ford算法(根据发明者 Richard Bellman 和 Lester Ford 命名)是求解单源最短路径问题的一种算法。单源点的最短路径问题是指:给定一个加权有向图G和源点s,对于图G中的任意一点v,求从s到v的最短路径。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为 Edward F. Moore zu 也为这个算法的发展做出了贡献。 与迪科
Bellman-Ford算法(根据发明者 Richard Bellman 和 Lester Ford 命名)是求解单源最短路径问题的一种算法。单源点的最短路径问题是指:给定一个加权有向图G和源点s,对于图G中的任意一点v,求从s到v的最短路径。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为 Edward F. Moore zu 也为这个算法的发展做出了贡献。

与迪科斯彻算法, (另一种著名的求最短路径的算法)不同的是,在Bellman-Ford算法中,路径的权值可以为负数。 设想从我们可以从图中找到一个环路(即从v出发,经过若干个点之后又回到v)且这个环路中所有路径的权值之和为负。那么通过这个环路,环路中任意两点的最 短路径就可以无穷小下去。如果不处理这个负环路,程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。

算法描述 设G为加权有向图 V是所有结点的集合 E是所有路径的集合 S表示源点 n表示V中所有结点的数目 weight(u,v)表示从结点u到结点v的路径的权值。 Distanz(v)表示从源点s出发到结点v的最短路径的距离,(或者说是从s到v所有的路径中权值的最小值)。Predecessor(v)表示节点 v的父结点

在Bellman-Ford算法结束之后,可以输出,G是不是包含一个负环路。如果G不包含负环路,那么Distanz就存储了从s出发到所有结点的距离。

Bellman-Ford算法的伪代码如下:
========================================
01 for 每一个结点v 属于 V
02 Distanz(v) := 无穷大, Predecessor(v) := null
03 Distanz(s) := 0,Predecessor(s):= null;

04 循环 n-1 次
05     for 每一条路径 (u,v)属于 E
06         if Distanz(u) + weight(u,v) < Distanz(v)
07         then
08            Distanz(v) := Distanz(u) + weight(u,v)
09            Predecessor(v) := u;

10 for 每一条路径 (u,v)属于 E
11     if Distanz(u) + weight(u,v) < Distanz(v)
12     then
13       中止程序并且返回 “找到负循环”
14 返回
==============================================
BF(G,w,s) // G = Graph, w = weight, s=source
Determine Single Source(G,s);
set Distance(s) = 0; Predecessor(s) = nil;
for each vertex v in G other than s,
   set Distance(v) = infinity, Predecessor(v) = nil;
for i <- 1 to |V(G)| - 1 do   //|V(G)| Number of vertices in the graph
   for each edge (u,v) in G do
      if Distance(v) > Distance(u) + w(u,v) then
         set Distance(v) = Distance(u) + w(u,v), Predecessor(v) = u; 
for each edge (u,r) in G do
   if Distance(r) > Distance(u) + w(u,r);
      return false; //This means that the graph contains a cycle of negative weight
                    //and the shortest paths are not well defined
return true; //Lengths of shortest paths are in Distance array
==============================================

bellman-ford(贝尔曼-福特)算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
地址:http://www.wutianqi.com/?p=1912 1.Dijkstra算法: http://www.wutianqi.com/?p=1890 2.Floy
最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++) 相关文章: 1.Dijkstra算法: http
转自:http://www.wutianqi.com/?p=1912 Dijkstra算法是处理单源最短路径的有效算法,但它局限于边
Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的
Bellman-Ford算法: 为了能够求解边上带有负值的单源最短路径问题,Bellman(贝尔曼)和Ford(福特)提出
原文: 算法起步之Bellman-Ford算法 从这篇开始我们开始介绍单源最短路径算法,他是图算法之一,我们
Bellman-Ford 算法及其优化SPFA Bellman-Ford算法与另一个非常著名的Dijkstra算法一样,用于求解单
 上一篇博文已经说了用dijkstra算法来求图(有向图和无向图)的最短路径了,那么怎么还需要使用
Bellman-Ford 算法是一种用于计算带权有向图中单源最短路径(SSSP:Single-Source Shortest Path)
前言 在最短路径问题中,约定图是一个带权值的有向图。最短路径是解决两节点之间的最小代价问题。最
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号