算法系列——贝尔曼福特算法（Bellman-Ford）

本系列旨在用简单的人话讲解算法尽可能避免晦涩的定义读者可以短时间内理解算法原理及应用细节。我在努力本篇文章编程语言为Python供参考。贝尔曼福特算法Bellman-Ford典型最短路径算法用于计算一个节点到其他节点的最短路径。Dijkstra算法也是基本原理逐遍的对图中每一个边去迭代计算起始点到其余各点的最短路径执行N-1遍最终得到起始点到其余各点的最短路径。N为连通图结点数与迪杰斯特拉算法的区别1. 迪杰斯特拉算法是借助贪心思想每次选取一个未处理的最近的结点去对与他相连接的边进行松弛操作贝尔曼福特算法是直接对所有边进行N-1遍松弛操作。2. 迪杰斯特拉算法要求边的权值不能是负数贝尔曼福特算法边的权值可以为负数并可检测负权回路。名词解释1. 松弛操作不断更新最短路径和前驱结点的操作。2. 负权回路绕一圈绕回来发现到自己的距离从0变成了负数到各结点的距离无限制的降低停不下来。1. 邻接矩阵构建基本用途用一个二维数组存放两两结点之间的距离或权值。2. 算法实现3. 最短路径的寻找同Dijkstra算法准备一路径数组更新时记录前驱结点。较为简单直接看也能看懂不太懂可以翻阅之前Dijkstra算法那篇博客算法系列——迪杰斯特拉算法Dijkstra4. 优化1. 提前跳出2. 队列优化见SPFA算法见另一篇博客算法系列——SPFA算法贝尔曼-福特算法的队列优化形式附全部源码#北京 天津 郑州 济南 长沙 海南 # 0 1 2 3 4 5 #模拟从文件中读入图的各个路径 a 0 1 500 0 2 100 1 2 900 1 3 300 2 3 400 2 4 500 3 4 1300 3 5 1400 4 5 1500 INF float(inf) N 6 weight [] def init(): global weight #定义邻接矩阵 记录各城市之间的距离 weight [[INF if j!i else 0 for j in range(N)] for i in range(N)] #解析数据 b [[int(i) for i in i.split( )] for i in a.split(\n) if i ! ] for i in b: weight[i[0]][i[1]] i[2] weight[i[1]][i[0]] i[2] init() def bellman_ford(src, target): dist [0 if i src else INF for i in range(N)] #用于记录最后更新结点 last_update [src if i ! INF else -1 for i in dist] #松弛n-1次因为最短路径的深度最多是n-1,n为结点数目 for i in range(N-1): change False #分别遍历边的两个顶点从而实现遍历所有边。 for j in range(N): for k in range(N): if dist[j] dist[k] weight[j][k]: dist[j] dist[k] weight[j][k] #记录更新该结点的结点编号 last_update[j] k #标记更改状态 change True #如果本轮未作出更改说明已完成 if not change: break #判断负权回路 for i in range(N): for j in range(N): if dist[j] dist[i] weight[j][i]: raise ValueError(存在负权回路) #输出从起点到终点的路径结点 tmp target path [] while tmp ! src: path.append(tmp) tmp last_update[tmp] path.append(src) print(-.join([str(i) for i in reversed(path)])) return dist[target]后记看了两个晚上第一个晚上看着看着放弃了今天晚上又鼓起勇气开写用了一晚上的时间现在是次日凌晨127终于完成了希望能对看完本文的各位有所帮助有所启发吧。我也在写的过程中不断学习不断变得更秃、变得更强晚安。本文大部分内容来自百度百科掺杂了一部分个人的理解和思考感谢完成该词条的大佬们写的很详细很易懂。 贝尔曼-福特算法