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

2023年5月17日 0 条评论 228 次阅读 1 人点赞

前言

Dijkstra算法是一种可以计算有向或无向图中单源最短路的算法。其工作模式与图的BFS(广度优先遍历)有些相似,通过类似于广度遍历的方式,逐渐从某个设定好的起点向外推进,一步步的计算出所有点到该点的距离。

本文不过多介绍Dijkstra单源最短路算法本身,如果仍然没有掌握该算法,可以先自行了解该算法的工作模式。下面提供一些可供参考的资料:

知乎:通俗易懂理解——dijkstra算法求最短路径

负权边对于Dijkstra算法的影响

Dijkstra算法工作模式

要了解该影响,首先需要明确Dijkstra算法的工作模式。其维护两个点集合。一个是“仍未确定最优解的点(S)”,一个是“已经确定最优解的点(U)”。且有一个重点:在算法工作期间内,如果某点被认为已经得到最优解,则该点会被从S移动到U,可以认为,从此以后该点已经被Closed(关闭),即解已经确定,且不容被更改。

为了方便,我们称在S中的点为opening vertex,U中的点为closed vertex

当图中出现负权边...

了解这一点后,让我们来看看下面这个图片示例,看看当负权边出现在图中时,可能会对算法造成什么影响:

Dijkstra计算带有负权边的图

如上图,假设我们尝试使用Dijkstra算法,计算该图中各个点距离C点的距离。

图中,绿色的点为closed vertex,白色的点为opening vertex,点上方的方框代表该点的,实时更新的计算距离。

1:算法首先锁定C点,将C点到C点的距离标记为0,并认定为最优解,然后根据C点尝试更新与其相连的opening vertex的距离(这里为A,B点,得到更新后距离是为1和5)。

2:剩余的opening vertex中,A距离出发点(C点)最小,距离为1,故锁定A点,(注意:锁定A点说明算法认为A点的最优解就是1,且之后算法也不可能再次更新A点的距离值,因为A点已经为Closed状态了),同时,锁定A点之后,再次更新与A点相连的opening vertex的值(与A点相连的点有B和C,但因为C点为closed vertex,故仅仅尝试更新B点的值),计算得到B点最新距离为min(5, 1+(-10)) = -9

3:最后,锁定B点,算法计算完成。

上方便是Dijkstra算法在示例图中的运行步骤和结果。不难发现,算法对于A点的最短距离出现了计算失误:实际上,A点的最短距离走法并不是C->A (1),而是C->B->A (-5)。

怎会如此?

分析之后可以发现,Dijkstra算法的核心,就在于每次都选择S集合中距离最小的点,并将其锁定,再通过这个点进一步更新其他点的距离。但为什么Dijkstra认为S集合中目前距离最小的点就是最优解呢?有没有可能从其他的点出发可以得到更小的距离呢?

比如在上述的示例图中,锁定C点后,算法认为A点的距离是1,B点的距离是5,所以A点的距离为1一定是最优解。那么有没有可能实际上1并不是C到A的最优解,我们通过B点走其他的路径最终可以得到更小的解呢?

答案是,当边的权值非负时,不可能,当边的权值存在负值时,则有可能。

当权值非负时,B点已经离出发点有5点的距离,所以所有从出发点出发经B点的路径,其长度必定大于等于5,但是当权值存在负数的时候,这一点就无法确定,经过B点的路径如果后续经过负权边,其路径长度总和也有可能再次小于5,此时,我们就无法确定C->A的1距离一定是最优解了,因为我完全有可能经由B路径得到一条总距离小于1的路径到达A。

上方的论证可能并不全面和严谨,不能作为Dijkstra算法相关特性的严格证明,但对我们进一步理解Dijkstra算法有着一些帮助。

一些有趣的说法

不难发现,实际上Dijkstra算法的设计和「贪心」有着很大的联系,实际上在S集合中选点就是一种贪心的行为。而我们都知道贪心算法的局限性,就是在部分情况下,其可能陷入局部最优解。而我们可以认为,当Dijkstra遇上负权边,就导致了其中贪心部分陷入了局部最优解(只考虑眼前的最短边(比如在5和10两条边中毫不犹豫的选择5),而忽略了目前看似落后的边未来的长期收益(比如那条权值为10的边链接的点,接下来将经过一条绝对值非常大的负权边-10000之类的),这也警示我们不要贪图眼前的小利,眼光应当长远(雾

如果我就是想拿下负权边呢?

噢亲爱的读者,相信我,不止你一个人有这种想法;实际上上百年前就已经有两名小伙想要拿下他,他们的名字分别是Richard Bellman 和Lester Ford Jr,接下来,就是Bellman Ford算法的表演时间了。

如果你对与这个Bellman Ford算法感兴趣,可以在互联网上找到很多关于这个算法的优质教程,其通过一次次迭代,对边进行Relaxation操作,实现了对于单源最短路径的求解,在本Blog的另外一篇文章「编程笔记」关于Bellman Ford单源最短路算法 中,也对这个算法做出了一些讨论,希望能对您产生一些帮助和启发。

NF

NF

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

文章评论(0)