「编程笔记」关于Bellman Ford单源最短路算法

2023年5月25日 0 条评论 152 次阅读 0 人点赞

开始之前

本Blog之前已经介绍过一种单源最短路算法——Dijkstra算法。但Dijkstra算法也有着自己的缺点,其中最明显的问题就是无法处理带负权边的图,其原因与其算法中包含的贪心原理有关。

而接下来介绍的算法,则拥有处理负权边的能力,该算法就是Bellman Ford单源最短路算法。该算法的核心思想是,对图中的每条边,都进行足够次数的Relaxation(松弛)操作,从而逐步推导出每个点距离出发点都最短路径长度。

关于Bellman Ford算法的原理和代码实现,网络中已有大量优秀的资料,这里便不再说明算法本身的详细工作流程。接下来着重说明一些Bellman Ford算法中一些限制条件,及其相关的一些理解。

Bellman Ford算法特性

当出现负权回路时...

在通过Bellman Ford算法计算单源最短路时,会要求所计算的图中不得存在权值为负值的回路。这个限制相对较好理解,下面举一个简单的例子。

如图,图中的A->B->C->A便是一个负权回路。而假设我们现在需要以A点作为出发点计算最短距离,请问A->D的最短距离应该是多少?不难发现这里出现了死循环。我们可以从原点出发,不停的走A->B->C->A这条路,每循环一次,我们距离出发点的距离就会越来越小。这也就意味着,只要我们的路径不断的在负权回路中重复足够多次,每一个点距离出发点的距离都可以认为是无穷小,这显然是不合理的。

负权回路对于图来说是存在特殊意义的,比如在经济学的部分领域中,“负权回路”是一个非常具有吸引力的词,因为可能代表着可持续的收益链,也可以代表着套利的机会,但Bellman Ford不认这些,在单元最短路算法的世界中,我们暂且不接受“套利机会”的存在。也就是说我们不允许待处理的图中出现负权回路,以此来保证计算结果是有意义的。

对于Bellman Ford算法的一些理解

迭代次数的理解

Bellman Ford算法的核心思想,在于每迭代一次,就对所有边进行遍历,并执行Relaxation操作。这里不难发现,迭代k次时,得到的结果,可以保证至少是路径条数为k时的最优解

为什么说是至少呢,因为其遍历的结果可能跟边遍历的顺序有关,如下图:

如图,我们发现对于图中的无向图,如果从左边的边开始遍历,实际上遍历一次之后我们就已经得到了最优解。而如果从右边开始遍历,我们就需要遍历3次才能得到最优解。

按照这个思路理解,不难推出,遍历k次时,得到的答案,只能保证,至少是路径条数为k限制下的最优解。

这里对路径条数做出说明,一个路径由多个边组成,上方所说的“路径条数”,指的是对于某条路径,其经过的边的个数的和。

为什么迭代次数等于点的个数?

上方我们已经论述了迭代次数k的意义,迭代k次时,得到的结果至少是路径条数k情况下的最优解,部分点的数据可能比会更优,但对于所有的点,只能保证其为路径条数k情况下的最优解。

那么我们到底需要迭代几次呢?根据定义,我们将问题转换成为:对于一个无向图,其某个点A到某个点B的全局最优路径中,最多可能经过几条边。

经过思考之后发现,最坏情况下,最优路径将会不重复的经过所有点。接下来对这个结论进行简单的说明:

首先是经过所有点。如果我们想要强迫最优路径经过尽可能多的点,最坏的情况之一,便是这个图形成了一个没有分叉的纯线性结构(就像上方对于迭代次数解释时所用图一样,每两个点用一条边链接,总边数为点数-1),这样从最左边到最右边的点,最优路径边毋庸置疑是经过所有的点。

其次是不重复。为什么我们可以确保最优路径中不会重复经过同一个点呢?这从某个角度上来说得益于算法前面的一个前提条件——不允许负权回路。想象一下,如果路径重复经过了同一个点,说明这个路径必定存在一段回路(从重复点出发,经过某个路径,又回到重复点)。而此时如果这个回路确定不是负权回路,那么说明如果跳过这段回路,我们可以得到一个权重更短的路径,反向说明了目前的路径不是最优路径。因而可以确定,如果一个路径被确定为最优路径,且该图中没有负权回路,那么这个路径绝对不会重复经过同一个点。

说明完毕,接下来让我们看看这两个结论,不难发现,不重复经过所有点,那么对于一个点个数为N的图,符合条件的路径,最长只能是N-1(因为一旦大于N-1,说明必定要产生回路,与条件冲突),所以最终确定,如果需要得到全局最优,其最少迭代次数为N-1。

综上所述,容易得到,算法的时间复杂度为O(N*M)。其中,N为点的个数,M为边的个数。

为什么它能攻克负权边?

在Dijkstra算法的文章中,笔者提到了一个观点,Dijkstra的核心是基于贪心的,而贪心带来了局部最优解这一隐患。带着这个角度再来看Bellman Ford算法,是否有一种熟悉的感觉?Bellman Ford算法的每次迭代都基于上一次的迭代结果。先知道路径条数1情况下的最优解,再根据此状态推出条数2情况下的解,以此类推最终得到路径条数为N-1时的最优解(也就是全局最优解),是不是有点「动态规划」的味道了呢?正是借助这这种工作模式,不像Dijkstra算法一样看到一点点甜头就着急的把点Close掉,Bellman Ford拥有了不被眼前甜美假象迷惑的能力,坚持着自己的本分,不断想着正确的道路一步步迈进,最终终于得到了令人满意的结果。

相关链接

GeeksForGeeks Bellman Ford算法介绍(英文)

「编程笔记」Dijkstra算法为什么无法处理带有负权边的图

NF

NF

NFのBlog 站长(超低技术力) ACG人,假期划水/追番ing...

文章评论(0)