procedure BellmanFord(list vertices, list edges, vertex source) // 读入边和节点的列表 // 初始化图 distance为∞,predecessor为空 for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // 对所有节点 for i from 1 to size(vertices)-1: //检查每条边 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // 检查是否有负权重的回路 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "图包含负权重的回路"
贝尔曼, 福特算法, 英語, bellman, ford, algorithm, 求解单源最短路径问题的一种算法, 由理查德, 貝尔曼和小萊斯特, 倫道夫, 福特创立, 有时候这种算法也被称为, moore, bellman, ford, 算法, 因为愛德華, 摩爾, 英语, edward, moore, 也为这个算法的发展做出了贡献, 它的原理是对图进行, displaystyle, 次松弛操作, 得到所有可能的最短路径, 其优于迪科斯彻算法的方面是边的权值可以为负数, 实现简单, 缺点是时间复杂度过高, 高达o. 贝尔曼 福特算法 英語 Bellman Ford algorithm 求解单源最短路径问题的一种算法 由理查德 貝尔曼和小萊斯特 倫道夫 福特创立 有时候这种算法也被称为 Moore Bellman Ford 算法 因为愛德華 F 摩爾 英语 Edward F Moore 也为这个算法的发展做出了贡献 它的原理是对图进行 V 1 displaystyle V 1 次松弛操作 得到所有可能的最短路径 其优于迪科斯彻算法的方面是边的权值可以为负数 实现简单 缺点是时间复杂度过高 高达O V E displaystyle O V E 但算法可以进行若干种优化 提高了效率 贝尔曼 福特算法概况類別最短路径问题 针对带权有向图 資料結構图复杂度最坏时间复杂度O V E displaystyle O left V E right 最优时间复杂度8 E displaystyle Theta E 空間複雜度O V displaystyle O V 相关变量的定义 目录 1 算法 1 1 偽代碼 2 原理 2 1 循环 2 2 负边权操作 2 3 负权环判定 3 尋找負迴路 4 优化 4 1 循环的提前跳出 4 2 队列优化 5 样例 6 参考文献算法 编辑 nbsp 在这个图中 假设A是起点 并且边以最坏的顺序处理 从右到左 需要 V 1 displaystyle V 1 nbsp 步或4 displaystyle 4 nbsp 次计算路径长度 相反地 若边以最优顺序处理 从左到右 算法只需要在一次遍历内完成 贝尔曼 福特算法与迪科斯彻算法类似 都以松弛操作为基础 即估计的最短路径值渐渐地被更加准确的值替代 直至得到最优解 在两个算法中 计算时每个边之间的估计距离值都比真实值大 并且被新找到路径的最小长度替代 然而 迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点 然后对其的出边进行松弛操作 而贝尔曼 福特算法简单地对所有边进行松弛操作 共 V 1 displaystyle V 1 nbsp 次 其中 V displaystyle V nbsp 是图的点的数量 在重复地计算中 已计算得到正确的距离的边的数量不断增加 直到所有边都计算得到了正确的路径 这样的策略使得贝尔曼 福特算法比迪科斯彻算法适用于更多种类的输入 贝尔曼 福特算法的最多运行O V E displaystyle O V cdot E nbsp 大O符号 次 V displaystyle V nbsp 和 E displaystyle E nbsp 分别是节点和边的数量 偽代碼 编辑 procedure BellmanFord list vertices list edges vertex source 读入边和节点的列表 初始化图 distance为 predecessor为空 for each vertex v in vertices if v is source then distance v 0 else distance v infinity predecessor v null 对所有节点 for i from 1 to size vertices 1 检查每条边 for each edge u v with weight w in edges if distance u w lt distance v distance v distance u w predecessor v u 检查是否有负权重的回路 for each edge u v with weight w in edges if distance u w lt distance v error 图包含负权重的回路 原理 编辑循环 编辑 每次循环操作实际上是对相邻节点的访问 第n displaystyle n nbsp 次循环操作保证了所有深度为n的路径最短 由于图的最短路径最长不会经过超过 V 1 displaystyle V 1 nbsp 条边 所以可知贝尔曼 福特算法所得为最短路径 负边权操作 编辑 与迪科斯彻算法不同的是 迪科斯彻算法的基本操作 拓展 是在深度上寻路 而 松弛 操作则是在广度上寻路 这就确定了贝尔曼 福特算法可以对负边进行操作而不会影响结果 负权环判定 编辑 因为负权环可以无限制的降低总花费 所以如果发现第n displaystyle n nbsp 次操作仍可降低花销 就一定存在负权环 尋找負迴路 编辑當使用這個算法尋找最短路徑時 有負迴路會使算法找不到正確的答案 但是 由於在找到負迴路後會中止算法 所以可以被用來尋找目標 例如在網路流分析中的消圈演算法 Cycle Cancellation Algorithms 优化 编辑循环的提前跳出 编辑 在实际操作中 贝尔曼 福特算法经常会在未达到 V 1 displaystyle V 1 nbsp 次前就出解 V 1 displaystyle V 1 nbsp 其实是最大值 于是可以在循环中设置判定 在某次循环不再进行松弛时 直接退出循环 进行负权环判定 队列优化 编辑 主条目 最短路径快速算法 西南交通大学的段凡丁于1994年提出了用队列来优化的算法 松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上 用一个队列记录松弛过的节点 可以避免了冗余计算 原文中提出该算法的复杂度为O k E displaystyle O k E nbsp k displaystyle k nbsp 是个比较小的系数 1 但该结论被证明不适于于所有情况 來源請求 Pascal语言示例 Begin initialize single source G s initialize queue Q enqueue Q s while not empty Q do begin u dequeue Q for each v adj u do begin tmp d v relax u v if tmp lt gt d v and not v in Q then enqueue Q v end end End C 语言示例int SPFA int s std queue lt int gt q bool inq maxn false for int i 1 i lt N i dis i 2147483647 dis s 0 q push s inq s true while q empty int x q front q pop inq x false for int i front x i 0 i e i next int k e i v if dis k gt dis x e i w dis k dis x e i w if inq k inq k true q push k for int i 1 i lt N i std cout lt lt dis i lt lt std cout lt lt std endl return 0 样例 编辑例 V v 1 v 2 v 3 v 4 E v 1 v 2 v 1 v 3 v 2 v 4 v 4 v 3 displaystyle V v 1 v 2 v 3 v 4 E v 1 v 2 v 1 v 3 v 2 v 4 v 4 v 3 nbsp w e i g h t v 1 v 2 1 w e i g h t v 1 v 3 3 w e i g h t v 2 v 4 3 w e i g h t v 4 v 3 1 displaystyle weight v 1 v 2 1 weight v 1 v 3 3 weight v 2 v 4 3 weight v 4 v 3 1 nbsp 运行如表 D Dist v P Pred v displaystyle D texttt Dist v P texttt Pred v nbsp 点 v 1 displaystyle v 1 nbsp v 2 displaystyle v 2 nbsp v 3 displaystyle v 3 nbsp v 4 displaystyle v 4 nbsp D P displaystyle D P nbsp D P displaystyle D P nbsp D P displaystyle D P nbsp D P displaystyle D P nbsp 初始化 0 null displaystyle 0 texttt null nbsp null displaystyle infty texttt null nbsp null displaystyle infty texttt null nbsp null displaystyle infty texttt null nbsp 循环第一次 0 null displaystyle 0 texttt null nbsp 1 v 1 displaystyle 1 v 1 nbsp 3 v 1 displaystyle 3 v 1 nbsp null displaystyle infty texttt null nbsp 循环第二次 0 null displaystyle 0 texttt null nbsp 1 v 1 displaystyle 1 v 1 nbsp 3 v 1 displaystyle 3 v 1 nbsp 2 v 2 displaystyle 2 v 2 nbsp 循环第三次 0 null displaystyle 0 texttt null nbsp 1 v 1 displaystyle 1 v 1 nbsp 1 v 4 displaystyle 1 v 4 nbsp 2 v 2 displaystyle 2 v 2 nbsp 参考文献 编辑 存档副本 2013 07 17 原始内容存档于2016 03 04 取自 https zh wikipedia org w index php title 贝尔曼 福特算法 amp oldid 78150893, 维基百科,wiki,书籍,书籍,图书馆,