您的位置:首页 > 游戏 > 游戏 > 企业网络营销策划平台_龙岩网站定制_上海网站seo公司_旺道seo推广系统怎么收费

企业网络营销策划平台_龙岩网站定制_上海网站seo公司_旺道seo推广系统怎么收费

2025/3/15 15:12:05 来源:https://blog.csdn.net/2301_77160836/article/details/144314350  浏览:    关键词:企业网络营销策划平台_龙岩网站定制_上海网站seo公司_旺道seo推广系统怎么收费
企业网络营销策划平台_龙岩网站定制_上海网站seo公司_旺道seo推广系统怎么收费

前言

   之前已经讲解了Dijkstra求最短路问题(点击查看),接下来讲解最短路问题中存在负权边的解法————Bellman - ford 算法。在这里插入图片描述   老规矩,通过详细例题来带大家学习Bellman - ford 算法。

题目:有边数限制的最短路

题目链接:AcWing 853. 有边数限制的最短路

给定一个 n n n个点 m m m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从 1 号点到 n n n 号点的最多经过 k k k 条边的最短距离,如果无法从 1 号点走到 n n n 号点,输出 impossible
注意:图中可能 存在负权回路

输入格式
第一行包含三个整数 n , m , k n,m,k n,m,k
接下来 $m $行,每行包含三个整数 x , y , z x,y,z x,y,z,表示存在一条从点 x x x 到点 y y y 的有向边,边长为 z z z
点的编号为 1 ∼ n 1∼n 1n

输出格式
输出一个整数,表示从 1 号点到 n n n 号点的最多经过 k k k 条边的最短距离。
如果不存在满足条件的路径,则输出 impossible

数据范围
1 ≤ n , k ≤ 500 , 1≤n,k≤500, 1n,k500,
1 ≤ m ≤ 10000 , 1≤m≤10000, 1m10000,
1 ≤ x , y ≤ n , 1≤x,y≤n, 1x,yn
任意边长的绝对值不超过 10000 10000 10000

输入样例:

3 3 1
1 2 1
2 3 1
1 3 3

输出样例:

3

Bellman - ford 算法

   ‌Bellman-Ford算法‌是由理查德·贝尔曼(Richard Bellman)和莱斯特·福特(Lester Ford)创立的,用于求解单源最短路径问题的一种算法。该算法可以处理包含负权边的图,这是其他最短路径算法如Dijkstra算法无法处理的。

   如下图所示,这就是最短路问题所应用到的所有算法,朴素Dijkstra算法堆优化版的Dijkstra算法在之前就已经讲过,而对于存在负权边问题,Dijkstra就无法进行解决了(下面会举个例子来说明),只能用Bellman - ford算法SPFA算法来解决。
在这里插入图片描述

   为什么Dijkstra就无法解决负权边问题? 如下图所示:

在这里插入图片描述

   dijkstra算法在图中走出来的最短路径是1 -> 2 -> 4 -> 5,算出 1 号点到 5 号点的最短距离是2 + 2 + 1 = 5,然而还存在一条路径是1 -> 3 -> 4 -> 5,该路径的长度是5 + (-2) + 1 = 4,因此 dijkstra 算法失效。

什么是Bellman - ford 算法?

   Bellman - ford 算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
   (通俗的来讲就是:假设 1 号点到 n 号点是可达的,每一个点同时向指向的方向出发,更新相邻的点的最短距离,通过循环 n-1 次操作,若图中不存在负环,则 1 号点一定会到达 n 号点,若图中存在负环,则在 n-1 次松弛后一定还会更新)

Bellman - ford 算法步骤

Bellman-Ford算法通过多次松弛操作来逐步逼近最短路径。算法的基本步骤如下:

  1. 初始化:将源点到所有点的距离设为无穷大,源点到自身的距离设为0。(初始化操作很简单,构建邻接表进行初始化。)

  2. 松弛操作:对图中的每条边进行V-1次遍历(V是顶点数),每次遍历都尝试通过某条边更新源点到其他顶点的距离。如果通过某条边可以缩短距离,则进行更新。

    加入每条边去松弛每个点到起点的距离(a到b的距离是w)

     dist[b] = min(dist[b], last[a] + w)
    

    松弛操作需要last数组,用来存储在前一轮迭代(或称为“松弛操作”)中计算得到的从源节点到各个节点的最短距离,也就是备份。这是因为在Bellman-Ford算法中,我们需要对每一条边进行多次迭代(松弛操作),以尝试更新从源节点到图中所有其他节点的最短路径。

    如果不加这个备份的话有可能会发生节点最短距离的串连;
    比如说:
    在这里插入图片描述
    现在从3号结点走到4号节点要想进行松弛操作就必须先得到dist[3],要想得到dist[3]就得知道dist[2];
    dist[2]=2,现在dist[3]是正无穷,用2号结点来更新3号结点,dist[3]=2+3=5;

    现在要更新dist[4]了,此时dist[4]=正无穷

    出现问题了,dist[4]是用dist[3]是用正无穷来更新还是5呢

    用dist[3]=5来更新那是下一次i迭代的事情;
    这道题说是不经过k条边,说不定下一次就到k条边了,所以还是得用正无穷来更新的

  3. 检测负环:如果在V-1次遍历后仍然可以更新某些顶点的距离,则说明图中存在负环,无法找到最短路径。

详细代码与注释

n, m, k = map(int, input().split())# 初始化边的列表,用于存储图中的边,每条边由三个元素组成:(起点, 终点, 权重)
edge = []# 设置一个足够大的值N,用于表示图中节点的数量上限(这里假设最多有100010个节点)
N = 100010# 初始化距离数组dist,用于存储从源节点(假设为节点1)到每个节点的最短距离
# 初始时,除了源节点到自身的距离为0外,其他所有节点的距离都设置为正无穷大
dist = [float('inf')] * N
dist[1] = 0# 读取m条边,每条边由三个整数组成:起点a,终点b,权重c
for i in range(m):a, b, c = map(int, input().split())edge.append((a, b, c))# 定义Bellman-Ford算法的函数
def bellman_ford():# 对图中的每条边进行k次松弛操作,尝试更新从源节点到每个节点的最短距离for i in range(k):# 复制上一轮迭代后的距离数组,用于比较更新前后的距离last = dist.copy()# 遍历每一条边,尝试通过当前边更新终点b的距离for j in range(m):a, b, w = edge[j]  # 当前边的起点a,终点b,权重w# 如果通过起点a到达b的距离比当前记录的b的距离更短,则更新b的距离dist[b] = min(dist[b], last[a] + w)# 检查是否存在从源节点到目标节点n的路径# 如果dist[n]仍然是正无穷大,则表示不存在这样的路径,返回'impossible'if dist[n] == float('inf'):return 'impossible'else:# 否则,返回从源节点到目标节点n的最短距离return dist[n]print(bellman_ford())

总结

   Bellman - ford 算法的时间复杂度是 O ( n m ) O(nm) O(nm),而对于负权边问题的最短路,还有一种更优的求解算法也就是SPFA算法,可以把时间复杂度降到 O ( m ) O(m) O(m),下一篇博客我们来学习SPFA算法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com