阿里云服务器做盗版电影网站,佛山网站哪家最专业,it产品网站建设方案,襄阳万家灯火网站建设相关文章#xff1a; 数据结构–图的概念 图搜索算法 - 深度优先搜索法#xff08;DFS#xff09; 图搜索算法 - 广度优先搜索法#xff08;BFS#xff09; 图搜索算法 - 拓扑排序 图搜索算法-最短路径算法-戴克斯特拉算法 贝尔曼-福特算法#xff08;Bellman-Ford#… 相关文章 数据结构–图的概念 图搜索算法 - 深度优先搜索法DFS 图搜索算法 - 广度优先搜索法BFS 图搜索算法 - 拓扑排序 图搜索算法-最短路径算法-戴克斯特拉算法 贝尔曼-福特算法Bellman-Ford
现在继续学习求解最短路径的第二种算法首先回想戴克斯特拉算法的例子每个边的权重都是正整数若出现负权重算法能不能正常运行呢看以下例子如图所示。
# 运行戴克斯特拉算法
g DijkstraGraph([A,B,C,D])
g.graph [[0, 1, 2, 10], [1, 0, 1, -20], [2, 1, 0, 0], [10, -20, 0, 0],];
g.dijkstra(0)# A作为源结点
#-------------结果----------------
结点 距离源结点的距离
A 0
B 1
C 2
D 10结果明显是错误的大家清楚知道结点【B】到结点【A】最短距离不是1它可以通过结点【D】到结点【A】此时最短距离为-10而且如果能够循环每次循环距离还能不断缩小变成一个死循环。既然戴克斯特拉算法没有办法计算负权重问题那有什么算法可以呢所以第二个算法正是能够处理此类问题它叫贝尔曼-福特Bellman–Ford算法。
贝尔曼-福特算法最大特点是支持负权重的情况它每次都会从源结点重新出发对每一个结点进行距离计算并更新最小距离而戴克斯特拉算法是从源结点出发向外扩逐个处理相邻的结点不会去重复处理结点从这也可以知道戴克斯特拉算法相对更高效一点。现在通过一个简单例子来观察贝尔曼-福特算法处理过程例子如下图所示。 1这次要处理的是有权有向图因此图的表示方式使用邻接列。首先初始化【distance】列表结点【A】为源结点它和自身的距离为0其余结点到源结点的距离为无穷大∞那么【distance】值为【0,∞,∞,∞,∞】如图所示。 2每一轮要计算每一个结点到源结点的距离一共要经过N-1轮边距离松弛N为结点数因为结点到源结点若连通最多就是N-1条边就可以达到。第一轮计算结点【A】一条边能到达的结点计算过程如表所示。 3根据上表得知现在【distance】值为【0,-1,∞,3,∞】。然后到第二轮计算结点【A】两条边能到达的结点计算过程如表所示。 4根据上表得知现在【distance】值为【0,-1,3,1,3】。然后到第三轮计算结点【A】三条边能到达的结点计算过程如表所示。 5根据上表得知现在【distance】值为【0,-1,3,1,1】。然后到第四轮由于结点数为5因此这是最后一轮5-14计算结点【A】四条边能到达的结点计算过程如表所示。 6根据上表得知现在【distance】值为【0,-1,3,1,1】最终结果如图所示。 从上面运算过程可知贝尔曼-福特算法要遍历每一个结点每次要对所有边进行松弛操作所以时间复杂度为O(N*E)N为结点数E为边数。在空间上只需要【distance】来记录结果因此空间复杂度为O(N)。
现在要用代码来表现上面的过程首先这是一个有权有向图可以创建【GraphPower】类来表示。然后创建【GraphBellmanFord】继承【GraphPower】类可以录入邻接列表bellman_ford()函数是算法的主程序其中用一个列表【distance】记录每个结点到源结点的距离print_result()函数格式化输出结果。
class GraphPower(): 有权图类def __init__(self, points):self.amount len(points) # 记录结点的总数self.points points # 记录结点位置和值的关系self.graph [] # 初始化图的邻接列表def add_edge(self, u, v, w):if u in self.points and v in self.points:index_u self.points.index(u)index_v self.points.index(v)self.graph.append([index_u, index_v, w]) # 录入数据else:print(录入数据有误)class GraphBellmanFord(GraphPower):贝尔曼-福特Bellman–Ford算法def print_result(self, dist): print(结点到源结点的距离) for i in range(self.amount): print({} \t {}.format(self.points[i], dist[i])) def bellman_ford(self, source):主程序贝尔曼福特算法求每个结点到源结点最短路径并且检查是否有负循环# 第一步初始化参数所有结点到源结点的距离为正无穷大 distance [float(Inf)]*self.amount # float(Inf)为正无穷大distance[source] 0 # 源结点本身距离为0# 第二步: 进行N-1次的边松弛找结点到源结点的最短距离for i in range(self.amount - 1):for u, v, w in self.graph:# distance(a) weight(ab)) distance(b) 说明存在有更短路径从a到b。if distance[u] ! float(Inf) and distance[u] w distance[v]: distance[v] distance[u] w # 更新最短路径# 第三步: 检查是否存在负循环,在完成这么N-1次松弛后如果还是可以松弛找到更短路径的话说明存在负循环for u, v, w in self.graph:if distance[u] ! float(Inf) and distance[u] w distance[v]: print(图包含负循环)returnself.print_result(distance) # 打印结果以例子为输入来测试程序。
g GraphBellmanFord([A,B,C,D,E]) # 初始化图记录结点值
g.add_edge(A,B, -1) # 添加边
g.add_edge(A,D, 3)
g.add_edge(B,D, 2)
g.add_edge(B,C, 4)
g.add_edge(B,E, 4)
g.add_edge(C,E, -2)
g.add_edge(E,B, 1)
g.add_edge(E,D, 5)
g.bellman_ford(0) # 按结点A为源结点计算结点的最短距离
#-------------------结果------------------------
结点到源结点的距离
A 0
B -1
C 3
D 1
E 1结果与手动过程计算出来的结果是一致的。如果修改结点【C】到结点【E】的值为-8也就是把第七行改为【g.add_edge(2, 4, -8)】再运行一次程序便能检查出负循环。大家可以多尝试其他例子加深算法的认识。
更多内容
想获取完整代码或更多相关图的算法内容请查看我的书籍《数据结构和算法基础Python语言实现》
